题目要求: 给定 n 个正整数, 请找出其中有多少个数 x 满足: 在这 n 个数中存在数 y, 使 y=kx, 其中 k 为大于 1 的整数输入描述 : 第一行输入一个 n, 接下来一行输入 n 个正整数 ai
输出描述: 输出符合条件个数
示例:
输入
5
1 2 3 4 5
输出
2
说明
5 个数中 1 和 2 符合条件, 1 是后面每个数的因子, 2 是 4 的因子
备注:
1n,ai1000000
解决 1:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1000005;
int cc[N];
bool can[N];
int getint()
{
char ch=getchar();
int res=0;
while((ch<'0' || ch>'9') && ch!='-')
ch=getchar();
bool neg=0;
if(ch=='-')
{
neg=1;
ch=getchar();
}
while('0'<=ch && ch<='9')
{
res=res*10+ch-'0';
ch=getchar();
}
if(neg)
res=-res;
return res;
}
int main()
{
int n,i,j;
n=getint();
for(i=1;i<=n;i++)
{
int now=getint();
cc[now]++;
}
int ans=0;
for(i=1;i<N;i++)
{
for(j=i+i;j<N;j+=i)
{
if(cc[j])
can[i]=1;
}
}
for(i=1;i<N;i++)
{
if(can[i])
ans+=cc[i];
}
cout<<ans<<endl;
return 0;
}
解决 2:
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1000001],b[2000001];
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
b[a[i]]++;
}
int sum=0;
sort(a,a+n);
for(i=1;i<a[n-1];i++){
if(b[i]){
for(int j=2;i*j<=a[n-1];j++)
if(b[i*j])
{sum+=b[i];break;}
}
}
printf("%d\n",sum);
}
找一找 (斐波那契数列)
来源: http://www.bubuko.com/infodetail-2485265.html