首页 > 代码库 > Codeforces 17D Notepad 简单数论
Codeforces 17D Notepad 简单数论
由题意可知,anw = (b-1)*b^(n-1)%c,则重点为求b^(n-1)。
弱渣推不出来只能上公示。
phi(c)为小于c且与c互质的个数。
当x >= phi(c)时:A^x = A(x%phi(c) + phi(c)) 。
当x < phi(c)时:直接求即可。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #include <ctime> #include <iomanip> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-6) #define _LL long long #define ULL unsigned long long #define LL __int64 #define INF 0x3f3f3f3f #define Mod 1000000007 /** I/O Accelerator Interface .. **/ #define g (c=getchar()) #define d isdigit(g) #define p x=x*10+c-'0' #define n x=x*10+'0'-c #define pp l/=10,p #define nn l/=10,n template<class T> inline T& RD(T &x) { char c; while(!d); x=c-'0'; while(d)p; return x; } template<class T> inline T& RDD(T &x) { char c; while(g,c!='-'&&!isdigit(c)); if (c=='-') { x='0'-g; while(d)n; } else { x=c-'0'; while(d)p; } return x; } inline double& RF(double &x) //scanf("%lf", &x); { char c; while(g,c!='-'&&c!='.'&&!isdigit(c)); if(c=='-')if(g=='.') { x=0; double l=1; while(d)nn; x*=l; } else { x='0'-c; while(d)n; if(c=='.') { double l=1; while(d)nn; x*=l; } } else if(c=='.') { x=0; double l=1; while(d)pp; x*=l; } else { x=c-'0'; while(d)p; if(c=='.') { double l=1; while(d)pp; x*=l; } } return x; } #undef nn #undef pp #undef n #undef p #undef d #undef g using namespace std; char s[1000010]; int B[1000010],N[1000010]; LL c,b,n; bool vis[1000010]; LL prime[1000010]; int Top; LL Euler(LL n) { LL ret=1,i; for(i=2; i*i<=n; i++) { if(n%i==0) { n/=i,ret*=i-1; while(n%i==0) n/=i,ret*=i; } } if(n>1) ret*=n-1; return ret; } LL Cal(int *n,LL c,bool &mark) { LL re = 0; for(int i = 0; n[i] != -1; ++i) { re *= 10,re += n[i]; if(re >= c) mark = true,re %= c; } return re; } LL qm(LL a,LL b,LL n) { LL ret=1; LL tmp=a; while(b) { if(b&1) ret=ret*tmp%n; tmp=tmp*tmp%n; b>>=1; } return ret; } int main() { int i,j; scanf("%s",s); for(i = 0; s[i] != '\0'; ++i) B[i] = s[i]-'0'; B[i] = -1; scanf("%s",s); for(i = 0; s[i] != '\0'; ++i) N[i] = s[i]-'0'; N[i] = -1; scanf("%I64d",&c); LL MAXN = sqrt(c); memset(vis,false,sizeof(vis)); Top = 0; for(i = 2; i <= MAXN; ++i) if(vis[i] == false) for(j = i+i,prime[Top++] = i; j <= MAXN; j += i) vis[j] = true; LL phi = Euler(c),b1; bool mark = false; b = Cal(B,c,mark); mark = false; n = Cal(N,phi,mark); b1 = (b-1+c)%c; if(mark == true) n = (n-1+phi)%phi + phi; else n--; LL anw = b1*qm(b,n,c)%c; if(anw == 0) anw = c; printf("%I64d\n",anw); return 0; }
Codeforces 17D Notepad 简单数论
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。