poj 2891 Strange Way to Express Integers

题目：http://poj.org/problem?id=2891

思路：扩展欧几里得

 

#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include <algorithm> using namespace std; #define maxn 100010 int n; long long a[maxn],b[maxn]; long long exgcd(long long a,long long b,long long &x,long long &y) {if(b==0){x=1;y=0;return a;}else{long long ans=exgcd(b,a%b,x,y);long long t=x;x=y;y=t-a/b*y;return ans;} } long long gcd(long long a,long long b) {if(b==0)return a;return gcd(b,a%b); } bool solve() {a[0]=a[1],b[0]=b[1];for(int i=2;i<=n;i++){long long a0=b[0];long long b0=b[i];long long c0=a[i]-a[0];long long x0,y0;long long r=gcd(a0,b0);if(c0%r!=0)return false;else{a0/=r;b0/=r;c0/=r;exgcd(a0,b0,x0,y0);x0*=c0;x0=(x0%b0+b0)%b0;a[0]=b[0]*x0+a[0];b[0]=b[0]*b0;}}return true; // a[0]为小于[b1,b2...bn]的非负整数解 } int main() {while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)scanf("%lld%lld",&b[i],&a[i]);if(solve())printf("%lld\n",a[0]);elseprintf("-1\n");}return 0; } View Code

 

转载于:https://www.cnblogs.com/overflow/p/3196113.html

总结

以上是生活随笔为你收集整理的poj 2891 Strange Way to Express Integers的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。