首页 > 代码库 > HDU 2879
HDU 2879
利用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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。