poj2891:Strange Way to Express Integers-阿里云开发者社区

开发者社区> 人工智能> 正文

poj2891:Strange Way to Express Integers

简介: 题目连接: 分明$excrt$就过了。 为什么还要仔细读题呢?    $qwq$ 反正我没读题然后被卡$long \ long +$输出格式错$……$总共$WA$了四次 怕不是要退役…… 上代码:   #include #include #include using na...

题目连接:

分明$excrt$就过了。

为什么还要仔细读题呢?   

$qwq$

反正我没读题然后被卡$long \ long +$输出格式错$……$总共$WA$了四次

怕不是要退役……

上代码:

 

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[100010],r[100010];
int n;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0) return x=1,y=0,a;
    long long tmp=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return tmp;
}
long long slove()
{
    long long M=a[1],R=r[1],x,y,d;
    for(int i=2;i<=n;i++)
    {
        d=exgcd(M,a[i],x,y);
        if((R-r[i])%d!=0) return -1;
        x=(R-r[i])/d*x%a[i];
        R-=x*M;
        M=M/d*a[i];
        R%=M;
    }
    return (R%M+M)%M;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
          scanf("%lld%lld",&a[i],&r[i]);
          printf("%lld\n",slove());
    }
    return 0;
}

 

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

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章