题解 P2613 【【模板】有理数取余】

题目链接

我们先看这个式子：

$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;//程序拜拜
}