【普及+/提高】洛谷P2613 【模板】有理数取余——快读+快速幂

题目来源

P2613 【模板】有理数取余 - 洛谷

题目描述

给出一个有理数 c=ba​，求 cmod19260817 的值。

这个值被定义为 bx≡a(mod19260817) 的解。

输入格式

一共两行。

第一行，一个整数 a。
第二行，一个整数 b。

输出格式

一个整数，代表求余后的结果。如果无解，输出 Angry!。

输入输出样例

输入 #1

233
666

输出 #1

18595654

说明/提示

对于所有数据，保证 0≤a≤1010001，1≤b≤1010001，且 a,b 不同时是 19260817 的倍数。

算法分析

由于此题数据超大，所以需要写一个快读函数

Code

​
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD=19260817;int read() { int x=0,f=1;char c=getchar();while(c<'0' || c>'9') { if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') { x=(x*10LL+c-'0')%MOD;c=getchar();}return x*f;
}LL fastPow(LL a,LL n,LL p) {LL ans=1;while(n) {if(n & 1) ans=ans*a%p;n>>=1;a=a*a%p;}return ans%p;
}int main() {int a=read();int b=read();if(b==0) cout<<"Angry!"<<endl;else cout<<a*fastPow(b,MOD-2,MOD)%MOD<<endl;
}​