2023 牛客国庆day4 【10.2训练补题】

 

目录

B-Basic Gcd Problem（素数筛+快速幂）

H-Harder Gcd Problem（素数）

---

 B-Basic Gcd Problem（素数筛+快速幂）

打表找规律发现答案为 (n质因子数目)^c 

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
const int inf=1<<30;
const ll mod=1e9+7;
inline void read(ll &x){ll f=1;x=0;char ch=getchar();while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}x*=f;
}
ll T,n,c;
int ct[N];
int su[N],cnt;
bool u[N];
void init(){memset(u,true,sizeof(u));cnt=0;for(int i=2;i<N;i++){if(u[i])su[++cnt]=i,ct[i]=1;for(int j=1;j<=cnt&&su[j]*i<N;j++){u[su[j]*i]=0;ct[su[j]*i]=ct[i]+1;//printf("ct[%d]%d\n",su[i]*j,ct[su[i]*j]);if(i%su[j]==0)break;}}
}
ll quickp(ll b,ll p){ll res=1;while(p){if(p&1)res=res*b%mod;p>>=1;b=b*b%mod;}return res;
}
int main(){init();read(T);while(T--){read(n);read(c);printf("%lld\n",quickp(c,ct[n]));}return 0;
} 

 

H-Harder Gcd Problem（素数）

参考题解：

【2020年牛客暑假第四场】H题 Harder Gcd Problem_2020牛客第四场 h题-CSDN博客

*所有数字都可由素数与其他数字相乘得到

*注意 v[ i ]标记时机

*偶数是素数2的倍数无需特判

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
const int inf=1<<30;
const ll mod=1e9+7;
inline void read(int &x){int f=1;x=0;char ch=getchar();while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}x*=f;
}
int T,n;
int v[N];int su[N],cnt;
bool u[N];
void init(){memset(u,true,sizeof(u));for(int i=2;i<N;i++){if(u[i])su[++cnt]=i;for(int j=1;j<=cnt&&su[j]*i<N;j++){u[su[j]*i]=0;if(i%su[j]==0)break;}}
}vector<pi>res;
vector<int>tmp;
int main(){read(T);init();while(T--){read(n);for(int i=2;i<=n;i++)v[i]=1;int ani;for(int i=1;su[i]*2<=n;i++)ani=i;for(int i=ani;i>0;i--){tmp.clear();for(int j=1;j*su[i]<=n;j++){int t=j*su[i];if(v[t]){tmp.push_back(t);}}int sz=tmp.size();if(sz&1){swap(tmp[1],tmp[sz-1]);}for(int j=0;j+1<sz;j+=2){res.push_back({tmp[j],tmp[j+1]});v[tmp[j]]=v[tmp[j+1]]=0;}}printf("%d\n",res.size());for(auto i:res)printf("%d %d\n",i.first,i.second);res.clear();}return 0;
}