牛客网 Wannafly挑战赛 A 找一找 思考题
链接：https://www.nowcoder.com/acm/contest/71/A
来源：牛客网
题目描述
给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数
输入描述:
第一行输入一个n
接下来一行输入n个正整数ai
输出描述:
输出符合条件个数
示例1
输入
5 1 2 3 4 5
输出
2
说明
5个数中1和2符合条件，1是后面每个数的因子，2是4的因子
备注:
1≤n,ai
≤1000000
emmmmm，直接上代码把，用下标记数组，第二层循环用倍增，因为是倍增，所以最坏的时间复杂度是n/2+n/3+n/4...+n/n，在10^8左右所以可以通过题目了
#include<queue> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define maxn 1000010 #define debug(a) cout << #a << " " << a << endl using namespace std; typedef long long ll; int a[maxn]; int main() { int n; while( cin >> n ) { memset(a,0,sizeof(a)); for( int i=0; i<n; i++ ) { int x; cin >> x; a[x] ++; //打标记 } int ans = 0; for( int i=1;i<=1000000;i++) { if( a[i] ) { for( int j=i+i; j<=1000000; j+=i ) { //倍增找倍数指 if( a[j] ) { ans += a[i]; break; } } } } cout << ans << endl; } return 0; }