数学知识()

数学知识()"/>

数学知识()

质数

试除法判定质数

给定 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;
}