数学知识()"/>
数学知识()
质数
试除法判定质数
给定 n 个正整数 ai,判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出格式
共 n 行,其中第 i 行输出第 i 个正整数 ai 是否为质数,是则输出 Yes
,否则输出 No
。
数据范围
1≤n≤100
1≤ai≤2^31−1
输入样例:
2
2
6
输出样例:
Yes
No
#include<iostream>
using namespace std;
//试除法 O(sqrt(n))
bool prime(int x)
{if(x<=1) return false;for(int i=2;i<=x/i;i++){if(x%i==0) return false;}return true;
}
int main()
{int n;cin>>n;while(n--){int a;cin>>a;if(prime(a)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}
分解质因数
给定 n 个正整数 ai,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出格式
对于每个正整数 ai,按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。
每个正整数的质因数全部输出完毕后,输出一个空行。
数据范围
1≤n≤100,
2≤ai≤2×10^9
输入样例:
2
6
8
输出样例:
2 1
3 12 3
x的质因子最多只包含一个大于根号x的数,如果有两个,两个质因数的乘积会大于x,矛盾
i 从 2 遍历到 根号x。 用 x / i,如果余数为 0,则 i 是一个质因
s 表示质因子 i 的指数,x /= i 为 0,则 s++, x = x / i
最后检查是否有大于 根号x 的质因子,如果有,输出
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
void divide(int x)
{for(int i=2;i<=x/i;i++){int s=0;if(x%i==0){while(x%i==0){s++;x/=i;}printf("%d %d\n",i,s);}}if(x>1) printf("%d 1\n",x);printf("\n");
}
int main()
{int n;cin>>n;while(n--){int x;cin>>x;divide(x);}return 0;
}
Divide and Equalize(cf)
考点分解质因数
给出了一个由n个正整数组成的数组a。可以对其执行以下操作:选择一对元素ai和aj(1≤i,j≤n ,i≠j);选择整数ai的除数之一,即整数x,使得ai mod x=0;将ai替换为ai/x,将aj替换为aj‧x。
通过应用一定次数的运算(可能为零)来确定是否可以使数组中的所有元素都相同。
输入数据:
7
5
100 2 50 10 1
3
1 1 1
4
8 2 4 2
4
30 50 27 20
2
75 40
2
4 4
3
2 3 1
输出数据:
YES YES NO YES NO YES NO
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
map<int,int>mp;
int main()
{int t;cin>>t;while(t--){int n;cin>>n;mp.clear();for(int i=1;i<=n;i++){int x;cin>>x;if(x==1) continue;for(int j=2;j<=x/j;j++){if(x%j==0){while(x%j==0){mp[j]++;x/=j;}}}if(x>1) mp[x]++;}int flag=0;for(auto it:mp){if(it.second%n!=0){flag=1;break;}}if(flag) cout<<"NO"<<endl;else cout<<"YES"<<endl;}return 0;
}
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N=1e4+10;
int a[N],b[N];
bool prime(int x)
{for(int i=2;i<=x/i;i++){if(x%i==0) return false;}return true;
}
map<int,int>mp;
int main()
{int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];mp.clear();for(int i=1;i<=n;i++){if(a[i]==1) mp[1]++;else{if(prime(a[i])) mp[a[i]]++;else{int num=a[i];for(int j=2;j<=num/j;j++){if(num%j==0){while(num%j==0){mp[j]++;num/=j;}}}if(num>1) mp[num]++;}}}int flag=0;for(auto t:mp){if(t.second%n!=0&&t.first>1){flag=1;break;}}if(!flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}
更多推荐
数学知识()
发布评论