首页 > 代码库 > HDU 2879

HDU 2879

2024-07-22 10:45:10   221人阅读

利用x<n的信息，可以证得当n为素数时，he[n]=2;同时，若n 为素数，则有HE[N^K]=2;因为若等式成立则有n|x(x-1)。抓住这个证即可。

至于符合积性函数，想了很久也没想出来，看了看网上的，觉得是不对的。

但试过几个数后，确实符合积性函数，就当是猜想吧。

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#define LL __int64using namespace std;const LL N=10000005;bool isprime[N];int pme[N],np;void initial(){	memset(isprime,true,sizeof(isprime));	np=0;	isprime[1]=false;	for(LL i=2;i<N;i++){		if(isprime[i]){			pme[np++]=i;			for(LL j=i*i;j<N;j+=i){				isprime[j]=false;			}		}	}}LL work(LL n){	LL rs=0;	for(int i=0;i<np&&pme[i]<=n;i++){		rs+=(n/pme[i]);	}	return rs;}LL quick(LL a,LL b,LL m){	LL res=1;	while(b){		if(b&1)		res=(res*a)%m;		b>>=1;		a=(a*a)%m;	}	return res;}int main(){	LL n,m;	int T;	initial();	scanf("%d",&T);	while(T--){		scanf("%I64d%I64d",&n,&m);		LL k=work(n);		LL ans=quick((LL)2,k,m);		printf("%I64d\n",ans);	}	return 0;}

　　

HDU 2879


联系
我们