AtCoder Beginner Contest 177 E.Coprime
程序员文章站
2022-06-12 19:50:13
...
AtCoder Beginner Contest 177 E.Coprime
这题我直接想到了质因数分解????,先素筛出 的质因数,然后对每个数质因数分解,每个质因数都标记一下,如果没有重复,那么这一组数肯定两两互质;如果重复,求这一组数的公因数,如果是 ,输出 ,否则输出 ,AC代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll a[N],prime[N],k,vis[N];
int n,flag=0;
bool isprime[N];
void Prime(){
fill(isprime,isprime+N,1);
k=0;
prime[1]=0;
for(ll i=2;i<N;i++){
if(isprime[i]){
prime[k++]=i;
for(ll j=2;i*j<N;j++)
isprime[i*j]=0;
}
}
}
void solve(ll n){
for(ll i=0;i<k&&prime[i]*prime[i]<=n;i++){
if(n%prime[i]==0){
if(vis[prime[i]]==0) vis[prime[i]]=1;
else{
flag=1;
return;
}
while(n%prime[i]==0){
n/=prime[i];
}
}
}
if(n>1){
if(vis[n]==0) vis[n]=1;
else{
flag=1;
return;
}
}
}
inline ll gcd(ll a,ll b)
{
return (a%b==0)?b:gcd(b,a%b);
}
int main(){
Prime();
cin>>n;
ll GCD=0;
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
if(!flag) solve(a[i]);
if(GCD==0) GCD=a[i];
else GCD=gcd(GCD,a[i]);
}
if(!flag) printf("pairwise coprime");
else if(flag&&GCD==1) printf("setwise coprime");
else printf("not coprime");
}
上一篇: vue2.0常见组件安装
下一篇: 使用位图法记录用户在一个月内的活跃情况
推荐阅读
-
AtCoder Beginner Contest 173(E 思维模拟 F 容斥 思维题 )
-
AtCoder Beginner Contest 163 D - Sum of Large Numbers(递推&找规律)
-
AtCoder Beginner Contest 182----C. To 3
-
AtCoder Beginner Contest 182----E. Akari
-
AtCoder Beginner Contest 182 题解
-
AtCoder Beginner Contest 182----D. Wandering
-
【Atcoder】Atcoder Beginner Contest 143
-
AtCoder Beginner Contest 176 D-Wizard in Maze(双端队列)
-
AtCoder Beginner Contest 176
-
AtCoder Beginner Contest 176总结