为啥通过率只有90%?没发现哪里出错了

#define first f
#define second s
#define ll long long
#define mp make_pair
#define pb push_back
#include<bits/stdc++.h>
#define pii pair<ll,ll>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=2e5+5;

ll a[maxn],r[maxn];
ll ex_gcd(ll a1,ll b1,ll &x,ll &y)
{
    if(b1==0){
        x=1;y=0;return a1;
    }
    ll r=ex_gcd(b1,a1%b1,x,y);
    ll t=x;x=y;
    y=t-a1/b1*y;
    return r;
}
ll CRT(int n)
{
    ll A=a[1],R=r[1],x,y,temp,d;
    for(int i=2;i<=n;i++){
        d=ex_gcd(A,a[i],x,y);
        if((R-r[i])%d){return -1;}
        temp=a[i]/d;
        x=x*((R-r[i])/d);
        x=(x%temp+temp)%temp;
        R-=A*x;
        A*=temp;
        R=(R%A+A%A);
    }
    return R==0?A:(R%A+A)%A;
}
int main()
{
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&a[i],&r[i]);
        }
        printf("%lld\n",CRT(n));
    }
    return 0;
}

全部评论
因为这一题的模数不互素,所以不能直接使用CRT进行计算,要预先处理一下 具体可以参考https://blog.csdn.net/winddreams/article/details/38425477
点赞 回复 分享
发布于 2020-02-10 13:40
题目链接::https://ac.nowcoder.com/acm/contest/1023/C
点赞 回复 分享
发布于 2020-02-09 11:46

相关推荐

07-17 12:09
门头沟学院 Java
讲的口干舌燥,头都晕了怎么要讲这么长啊
码农索隆:没事,你口干舌燥,他不一定会看,
投递小鹏汽车等公司7个岗位
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务