我們先看這個式子:
$c=\dfrac{a}{b}$ $ $ $ $ $mod$ $ $ $ $ $19260817$
某正常高中生:這$……$
---
對于這個 $c$ 。
顯然,它很可能是小數。
那麼, $double$ 的取餘你老師講過麼$?!!!$
是以,我們要~~化簡~~魔改一下這個式子。
$$c=\dfrac{a}{b}=a*b^{-1}$$
又因為是 $mod$ $ $ $p=19260817$ 的意義下的計算。
是以,現在就有了一種化小數為整數的方法:
乘法逆元
$c=a*b^{-1}≡a*b^{p-2}$ $ $ $ $ $ mod $ $ $ $ $ $ p $
而在這裡, $ p $ $ = $ $ 19260817 $
并且,當 $b^{p-2}≡0$ $ $ $ $ $ mod $ $ $ $ $ $ p $ 時,
分母為 $0$ ,無解。
是以答案就出來了。
好了,天真的認為我~~們~~以為這樣就行了。
然而$……$
$0≤a,b≤10^{10001}$
高精模低精按位先模到 $int$ 或 $long$ $ $ $ long$ 以内,在做。
然後調了三天終于$A$了。
本寶寶在這裡在吐槽一番:
定義變量忘了初始化$……$
資料出鍋玄學$RE$ $……$
也是沒誰了。
上代碼:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int p=19260817;
int a[10100];
int b[10100];
char a1[10100];
char b1[10100];
int l1,l2;
int len1,len2;
long long x,y;
long long pow2(long long a,long long b)
{
long long res=1;
for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;
return res%p;
}
void calculet_1()
{
long long num=0;
for(int i=len1;i<=len1+8;i++)
num*=10,num+=a[i];
num%=p;
for(int i=len1+8;i>=len1;i--)
{
int now=num%10;num/=10;
a[i]=now;
}
for(int i=0;i<=8;i++) if(a[len1+i]!=0){len1+=i;break;}
}
void calculet_2()
{
long long num=0;
for(int i=len2;i<=len2+8;i++)
num*=10,num+=b[i];
num%=p;
for(int i=len2+8;i>=len2;i--)
{
int now=num%10;num/=10;
b[i]=now;
}
for(int i=0;i<=8;i++) if(b[len2+i]!=0){len2+=i;break;}
}
signed main()
{
// freopen("testdata.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%s",a1);
scanf("%s",b1);
// printf("%s\n",b1);
l1=strlen(a1);
l2=strlen(b1);//輸入以及處理資料。
for(int i=0;i<l1;i++)
a[i]=a1[i]-'0';
for(int i=0;i<l2;i++)
b[i]=b1[i]-'0';//将char 變int(個人不習慣用char做運算)
while(l1-len1>=10) calculet_1();
while(l2-len2>=10) calculet_2();//計算,我是從高位到低位依次減的,可以省時間。
for(int i=len1;i<l1;i++) x*=10,x+=a[i];
for(int i=len2;i<l2;i++) y*=10,y+=b[i];
x%=p;y%=p;//計算取模之後的值。
// printf("%lld\n",y);
if(x==0){puts("0");return 0;}
if(y==0){puts("Angry!");return 0;}//特判
long long ans=pow2(y,p-2);
// printf("%lld\n",ans);
ans=(ans*x)%p;
printf("%lld",ans);//計算答案和輸出
return 0;//程式拜拜
}