class="markdown_views prism-github-gist"> 扔扔扔https://www.luogu.org/problemnew/show/P2613
上面是题目，首先题目暴力、粗暴简短明了,还有带有政治敏感
这题主要就是要求b的逆元
首先我们观察一下这个模数19260817是个质数（下面我们用模数来代替这个数字），所以根据我们伟大的费马小定理，可以直接得出 b 的逆元就是 b^p-2，怎么推出来的呢，就是因为费马小定理是 a^p-1≡1（mod p）,当p为质数的时候成立，我们就把b带进去，b^p-1 ≡ 1 (mod p ) 所以可以直接用快速幂求辣。
等等。。。当b为p的倍数的时候是不成立的（没有逆元）
代码： #include #define ll long long #define mod 19260817 using namespace std; char st[10005]; int main(){ scanf("%s",st);//根本不用高精度，在输入的时候模就好了 int len=strlen(st); int a=0; for(int i=0;i*10+st[i]-'0'; a=a%mod; } scanf(" %s",st); len = strlen(st); int b=0; for(int i=0;i*10+st[i]-'0'; b=b%mod; } ll ans=1; ll t=b; if(t%mod==0) {printf("Angry!");return 0;}//如果是模数的倍数就呵呵 for(int i=mod-2;i;i>>=1,t=t*t%mod) if(i&1) ans=ans*t%mod;//快速幂 ans=ans*a%mod; printf("%lld",ans); //哈哈 return 0; } //别走，还有扩欧的 求逆元嘛，我们还可以用扩展欧几里得啊 我们知道，扩展欧几里得是用来求ax + by = gcd(a, b) 这类问题的，那么对于求逆元，ax ≡ 1(mod b) ,可以转换成 ax + by = 1,当然这里a,b也要是互质的，所以x就是a关于mod b意义下的逆元辣。
又可以开始写辣 #include #define ll long long #define mod 19260817 using namespace std; char st[10005]; ll exgcd(ll &x,ll &y,ll a,ll b,ll &d){ //正常的扩展欧几里得 if(!b) {d=a;x=1;y=0;} else { exgcd(x,y,b,a%b,d); int t=x; x=y;y=t-(a/b)*y; x=x%mod;y=y%mod; } } int main(){ scanf("%s",st);//输入同上 int len=strlen(st); int aa=0; for(int i=0;i10+st[i]-'0'; aa=aa%mod; } scanf(" %s",st); len = strlen(st); int bb=0; for(int i=0;i10+st[i]-'0'; bb=bb%mod; } ll x,y,a,b,d; a=bb;b=mod; exgcd(x,y,a,b,d); //求b关于模数的逆元 if(d>1) {printf("Angry!");return 0;} for(;x<0;) x+=mod; //最好把x变为正数 ll ans=aa*x%mod; printf("%lld",ans);//输出 return 0; } 真开心啦啦啦啦啦啦啦啦辣