本文主要是介绍悬赏征答问题降临，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
请问P4777哪里有问题？
#include <bits/stdc++.h>
using namespace std;typedef long long ll;ll gsc(ll x, ll y, ll z)
{if(y == 0) return 0;ll ans = gsc(x, y / 2, z);ans = (ans + ans) % z;if(y % 2 == 1) ans = (ans + x) % z;return ans;
}ll gcd(ll a, ll b)
{return b ? gcd(b, a % b) : a;
}ll a[100010];
ll b[100010];ll lcm(ll a, ll b)
{return a / gcd(a, b) * b;
}ll exgcd(ll a, ll b, ll & x, ll & y)
{if(b == 0){x = 1;y = 0;return a;}ll g, xp, yp;g = exgcd(b, a % b, xp, yp);x = yp;y = xp - yp * (a / b);return g;
}void merge(ll & a1, ll & b1, ll a2, ll b2)
{ll l = lcm(a1, a2);ll g = gcd(a1, a2);ll k1p, k2p;g = exgcd(a1, a2, k1p, k2p);ll k = (b2 - b1) / g;ll k1 = gsc(k1p, k, l);ll x = gsc(k1, a1, l);x = ((x + b1) % l + l) % l;a1 = l;b1 = x;
}int main()
{int n;cin >> n;for(int i = 1; i <= n; i ++) scanf("%lld%lld", &a[i], &b[i]);for(int i = 1; i <= n; i ++) b[i] %= a[i];for(int i = 2; i <= n; i ++) merge(a[i], b[i], a[i - 1], b[i - 1]);printf("%lld\n", b[n]);return 0;
}我刚刚用了__int128就过了
但是这样写样例输出17
这篇关于悬赏征答问题降临的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
