题解 P2613 【【模板】有理数取余】-阿里云开发者社区

开发者社区> 大数据> 正文

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

简介: 题目链接 我们先看这个式子:$c=\dfrac{a}{b}$ $ $ $ $ $mod$ $ $ $ $ $19260817$某正常高中生:这$……$---对于这个 $c$ 。显然,它很可能是小数。那么, $double$ 的取余你老师讲过么$?!!!$所以,我们要~~化简~~魔改一下这个式子。

题目链接

我们先看这个式子:

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

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
大数据
使用钉钉扫一扫加入圈子
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章