转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4335
大意找出多少个N满足下式
范围如此之大啊。结果做法是暴力,囧。
要用到一个降幂公式:http://blog.csdn.net/acm_cxlove/article/details/7829367
A^x = A^(x % Phi(C) + Phi(C)) (mod C) (x>=Phi(C))
注意括号里的条件,那么当n比较小的时候,就不能用这个了,n比较小,肯定是暴力嘛。
那么第一个阶段便是当n比较小,n!小于phi(p),直接暴力求解。
当n!大于phi(P)的时候,便 可以用上面的降幂公式。还得继续暴力,发现n!%phi(p)会出现0,这是必然的,至少n>=phi(p)为0
,
那么(n+1)!%phi(p)也为0,这便出现了重复,转变为n^(phi(p))%p==b的问题了。固定了指数,根据鸽巢原理,余数是循环的,那么只
要找出p个的结果,之后通过循环节求解便可以了。
当P为1的时候,b为0,这时候答案是m+1,不过m可能为2^64-1,如果加1的话就溢出了,这里太坑了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define LL unsigned long long
//#define MOD 1000000007
#define eps 1e-6
#define zero(a) fabs(a)<eps
using namespace std;
LL get_eular(LL m){
LL ret=1;
for(LL i=2;i*i<=m;i++)
if(m%i==0){
ret*=i-1;
m/=i;
while(m%i==0){
m/=i;
ret*=i;
}
}
if(m>1)
ret*=m-1;
return ret;
}
LL PowMod(LL a,LL b,LL MOD){
LL ret=1;
while(b){
if(b&1)
ret=(ret*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return ret;
}
LL b,p,m,ring[100005];
int main(){
int t,cas=0;
scanf("%d",&t);
while(t--){
scanf("%I64u%I64u%I64u",&b,&p,&m);
printf("Case #%d: ",++cas);
if(p==1){
//大坑一个,要注意溢出
if(m==18446744073709551615ULL)
printf("18446744073709551616\n");
else
printf("%I64u\n",m+1);
continue;
}
LL i=0,phi=get_eular(p),fac=1,ans=0;
//第一个环节,n!<phi(p)
for(i=0;i<=m&&fac<=phi;i++){
if(PowMod(i,fac,p)==b)
ans++;
fac*=i+1;
}
fac=fac%phi;
//第二个环节,n^(n!%phi(p)+phi(p)),直到指数固定为phi(p)
for(;i<=m&&fac;i++){
if(PowMod(i,fac+phi,p)==b)
ans++;
fac=(fac*(i+1))%phi;
}
if(i<=m){
LL cnt=0;
//打表一个循环
for(int j=0;j<p;j++){
ring[j]=PowMod(i+j,phi,p);
if(ring[j]==b)
cnt++;
}
LL idx=(m-i+1)/p;
ans+=cnt*idx;
LL remain=(m-i+1)%p;
for(int j=0;j<remain;j++)
if(ring[j]==b)
ans++;
}
printf("%I64u\n",ans);
}
return 0;
}
分享到:
相关推荐
2017hdu多校联合训练第一场标程及数据
2019 Multi-University Training Contest 4(2019hdu多校第五场数据与标程),欢迎大家下载
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
HDU2013暑期多校联合训练第一场0723-解题报告和标程
ACM/ICPC 2010年多校联合第十场第九题的解题报告及代码,AC代码有三个,最好的是src
有2019 Multi-University Training Contest 4,hdu多校第四场的题解,数据标程,有需要的可以下载哦
hdu 6045 Is Derek lying? 6046 hash 6047 Maximum Sequence 6048 Puzzle 6049 Sdjpx Is Happy 6050 Funny Function 6051 If the starlight never fade 6052 To my boyfriend 6053 TrickGCD 6054 String ...
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
2014 Multi-University Training Contest 1多校联合赛标程和部分数据。
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...