CF 17D - Notepad如何利用数论取模和欧拉函数解决问题？

本文共计656个文字，预计阅读时间需要3分钟。

D+-Notepad+Time+Limit:2000MSMemory+Limit:65536KB

64bit+IO+Format:%25I64d+%25I64u

Submit+Status+PracticeCodeForces+17D描述：Nick+对一切非传统的事物都感兴趣。

D -Notepad

Time Limit:2000MSMemory Limit:65536KB64bit 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 basebcaught his attention. Before he starts studying it, he wants to write in his notepad all the numbers of lengthnwithout leading zeros in this number system. Each page in Nick's notepad has enough space forcnumbers exactly. Nick writes every suitable number only once, starting with the first clean page and leaving no clean spaces. Nick never writes number0

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 integersb,nandc(2 ≤ b < 10¹⁰⁶,1 ≤ n < 10¹⁰⁶,1 ≤ c ≤ 10⁹). 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 exactly4numbers of length3in binary number system. In the first sample Nick writes3numbers on the first page and1on the second page. In the second sample all the4

思路： 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"; }}