快速链接
原题链接
题目大意
给出一个有理数 c = a b c=\frac ab c=ba，求 c m o d 19260817 c\bmod 19260817 cmod19260817。
输入格式
一共两行。
第一行一个整数
a
a
a。
第二行一个整数
b
b
b。
输出格式
一个整数，代表求余后的结果。如果无解，输出Angry!。
S a m p l e \mathbf{Sample} Sample I n p u t \mathbf{Input} Input
233
666
S a m p l e \mathbf{Sample} Sample O u t p u t \mathbf{Output} Output
18595654
H
i
n
t
&
E
x
p
l
a
i
n
\mathbf{Hint\&Explain}
Hint&Explain
无
数据范围
对于
100
%
100\%
100%的数据，
0
≤
a
≤
1
0
10001
,
1
≤
b
≤
1
0
10001
0\le a\le 10^{10001},1\le b\le 10^{10001}
0≤a≤1010001,1≤b≤1010001。
a
,
b
a,b
a,b 不同时是
19260817
19260817
19260817 的倍数。
解题思路
首先，你需要知道…
1.
费
马
小
定
理
\large\sf1.费马小定理
1.费马小定理
当
p
p
p 为质数，且正整数
a
a
a 与
p
p
p 不互质时，
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}\equiv 1\pmod p
ap−1≡1(modp)。
换句话说，就是
a
p
−
2
≡
a
−
1
(
m
o
d
p
)
(1)
a^{p-2}\equiv a^{-1}\pmod p \tag{1}
ap−2≡a−1(modp)(1)
现在进入正题。
把原式
c
=
a
b
c=\frac ab
c=ba 改一下，就可以得到
c
=
a
⋅
b
−
1
c=a\cdot b^{-1}
c=a⋅b−1
因为
19260817
19260817
19260817 是一个质数，则可以把
(
1
)
(1)
(1) 代入得
c
=
a
⋅
b
p
−
2
c=a\cdot b^{p-2}
c=a⋅bp−2
直接套一个快速幂就可以过了。
但是，不要着急，题目说了还会有无解的情况。
问题是，在什么情况下
a
b
\frac ab
ba会无解呢？
很容易可以想到，当
b
=
0
(
m
o
d
p
)
b=0\pmod p
b=0(modp) 时无解。
判断一下
b
(
m
o
d
p
)
b\pmod p
b(modp) 是否为
0
0
0 即可。
最后，还有最重要的一步，就是读入。
数据范围给的上限是
1
0
10001
10^{10001}
1010001 ，所以要在读入的时候，边读入边模，达到读入后
a
,
b
a,b
a,b 都在
p
p
p 以内的效果。
上代码
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
#define int long long
int power(int a,int b,int p)
{
int tar=1;
while(b)
{
if(b&1)
tar=(tar*a)%p;
a=(1ll*a*a)%p;
b>>=1;
}
return tar;
}
int read(int p)
{
int tar=0;
string s;
cin>>s;
for(int i=0; i<s.size(); i++)
tar=(tar*10+s[i]-'0')%p;
return tar;
}
const int p=19260817;
int a,b;
signed main()
{
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
/* Code */
a=read(p);
b=read(p);
if(b==0)
cout<<"Angry!"<<endl;
else
cout<<(a*power(b,p-2,p))%p<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
完美切题 ∼ \sim ∼