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

 

目录

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

H-Harder Gcd Problem（素数）

---

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

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

#include
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'
		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
		if(u[i])su[++cnt]=i,ct[i]=1;
		for(int j=1;j<=cnt&&su[j]*i
			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
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'
		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
		if(u[i])su[++cnt]=i;
		for(int j=1;j<=cnt&&su[j]*i
			u[su[j]*i]=0;
			if(i%su[j]==0)break;
		}
	}
}
 
vectorres;
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+12){
				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;
}