D - Notepad
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit Status Practice CodeForces 17D
Description
Nick is attracted by everything unconventional. He doesn't like decimal number system any more, and he decided to study other number systems. A number system with base b caught his attention. Before he starts studying it, he wants to write in his notepad all the numbers of length n without leading zeros in this number system. Each page in Nick's notepad has enough space for c numbers exactly. Nick writes every suitable number only once, starting with the first clean page and leaving no clean spaces. Nick never writes number 0
Would you help Nick find out how many numbers will be written on the last page.
Input
The only input line contains three space-separated integers b, n and c (2 ≤ b < 10106, 1 ≤ n < 10106, 1 ≤ c ≤ 109). You may consider that Nick has infinite patience, endless amount of paper and representations of digits as characters. The numbers doesn't contain leading zeros.
Output
In the only line output the amount of numbers written on the same page as the last number.
Sample Input
Input
2 3 3
Output
1
Input
2 3 4
Output
4
Hint
In both samples there are exactly 4 numbers of length 3 in binary number system. In the first sample Nick writes 3 numbers on the first page and 1 on the second page. In the second sample all the 4
思路： ab%c=a*10%c+b%c;
#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<vector>using namespace std;const int mm=3e6+7;char b[mm],s[mm];long long c;long long mod(long long a,long long b)///a^b%c{ long long z=1; while(b) { if(b&1) z=(z*a)%c; a=(a*a)%c; b/=2; } return z;}long long phi(long long n)///欧拉函数与n互质的个数{ long long rea=n; for(int i=2;i*i<=n;i++) if(n%i==0) { rea=rea-rea/i; do n/=i; while(n%i==0); } if(n>1) rea=rea-rea/n; return rea;}int main(){ long long bb,nn,lb,ls; while(cin>>b>>s>>c) { bb=0;nn=0; lb=strlen(b);ls=strlen(s); int zz=phi(c); for(int i=0;i<lb;i++) { bb=(bb*10+b[i]-'0')%c; } bool yes=0; for(int i=0;i<ls;i++) { nn=nn*10+s[i]-'0'; if(nn>zz) {yes=1;nn=nn%zz; } } if(yes) nn+=zz; --nn; long long z=0; if(bb==0)bb=c; z=mod(bb,nn); z=(((bb+c-1)%c)*z)%c; if(z!=0) cout<<z<<"\n"; else cout<<c<<"\n"; }}