很容易得出答案就是2^(n-1)
但是N暴大,所以不可以直接用幂取模,因为除法操作至少O(len)了,总时间会达到O(len*log(N)) 显然爆的一塌糊涂
套用FZU1759的模板+顺手写一个大数-1
http://acm.fzu.edu.cn/problem.php?pid=1759
标程的做法是用费马小定理 , a≡1(mod p)
那么2%(1e9+7) = 1
很容易得出 2%(10e+7) = 2%(10e+7)
然后就能用快速幂了 但FZU那题显然不是这么水的...我暂时也没看懂是怎么做的
现在看懂这个意思了,根据著名的欧拉公式:A^PHI(C)=1(MOD C) 条件:(A,C)=1
我们可以得出以下公式
那么这题就能做了..显然是以Phi(c)作为循环节 ... 但我还是没理解当(A,C)!=1时这个公式的成立性 ....prpr
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define LL long long
#define nnum 100005
#define nmax 131625
int flag[nmax], prime[nmax];
char ch[nnum];
int plen;
void mkprime() {
int i, j;
memset(flag, -, sizeof(flag));
for (i = , plen = ; i < nmax; i++) {
if (flag[i]) {
prime[plen++] = i;
}
for (j = ; (j < plen) && (i * prime[j] < nmax); j++) {
flag[i * prime[j]] = ;
if (i % prime[j] == ) {
break;
}
}
}
}
int getPhi(int n) {
int i, te, phi;
te = (int) sqrt(n * 1.0);
for (i = , phi = n; (i < plen) && (prime[i] <= te); i++) {
if (n % prime[i] == ) {
phi = phi / prime[i] * (prime[i] - );
while (n % prime[i] == ) {
n /= prime[i];
}
}
}
if (n > ) {
phi = phi / n * (n - );
}
return phi;
}
int cmpCphi(int p, char *ch) {
int i, len;
LL res;
len = strlen(ch);
for (i = , res = ; i < len; i++) {
res = (res * + (ch[i] - ''));
if (res > p) {
return ;
}
}
return ;
}
int getCP(int p, char *ch) {
int i, len;
LL res;
len = strlen(ch);
for (i = , res = ; i < len; i++) {
res = (res * + (ch[i] - '')) % p;
}
return (int) res;
}
int modular_exp(int a, int b, int c) {
LL res, temp;
res = % c, temp = a % c;
while (b) {
if (b & ) {
res = res * temp % c;
}
temp = temp * temp % c;
b >>= ;
}
return (int) res;
}
void solve(int a, int c, char *ch) {
int phi, res, b;
phi = getPhi(c);
if (cmpCphi(phi, ch)) {
b = getCP(phi, ch) + phi;
} else {
b = atoi(ch);
}
res = modular_exp(a, b, c);
printf("%d\n", res);
}
char* sub(char ch[]){
int len = strlen(ch);
int fl = ;
char x[nnum];
for(int i = len- ; i >= ; i--){
x[i] = ((ch[i] - fl - '') + ) % + '';
if((ch[i] - fl - '') < ) fl = ;
else fl = ;
}
x[len] = '\0';
if(x[] == '') return x+;
return x;
}
int main() {
int a = , c = ;
mkprime();
while (~scanf("%s",ch)) {
char x[nmax];
strcpy(x,sub(ch));
//puts(x);
solve(a % c, c, x);
}
return ;
}