exgcd,遇到了奇奇怪怪的问题……
查看原帖
exgcd,遇到了奇奇怪怪的问题……
369704
SUITLIE楼主2021/7/19 20:35

rt.
第一次交,代码注释的位置前半段写的是if(x>=0) ans+=b[i]*m[i]*x;,爆了#2,#3,#4,#9四个点。
于是我本着玄学改错的宗旨改成了ans+=b[i]*m[i]*((x<0)?(x+a[i]):x);,直接切了……
然后我试了试if(x<0) ans+=b[i]*m[i]*(x+a[i]);,也切了,然而这不是互逆的判断条件吗……区别在哪里……
求神犇指点(((
附上60分代码:


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	ll temp=x;
	x=y;
	y=temp-a/b*y;
	return;
}

//......这题不用求GCD

int n,a[15],b[15],m[15];
ll ans,M=1;
	
int main()
{
	scanf("%d",&n);
	for(register int i=0;i<n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		M*=a[i];
	}
	for(register int i=0;i<n;i++)
	{
		m[i]=M/a[i];
		ll x=0,y=0;
		exgcd(m[i],a[i],x,y);
        //········注释················
		if(x>=0)
		ans+=b[i]*m[i]*x;
		else
		ans+=b[i]*m[i]*(x+a[i]);
        //········注释················
	}
	ans%=M;
	printf("%lld",ans);
	return 0;
}
2021/7/19 20:35
加载中...