神奇代码删了判无解才能过
查看原帖
神奇代码删了判无解才能过
747882
_adil_楼主2024/5/23 19:48

rt,删了73行的判断无解输出‘nooooo’才能过,否则最后三个点会误判无解wa...这是咋回事啊

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<math.h>
#include<set>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
#include<iterator>
#define N 200009
#define INF 0x3f3f3f3f
#define mod 998244353
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef __int128 spint;
typedef pair<int,int> pii;
spint n,cur,pos=1;
struct node{
	spint r,m;
}a[N];
inline spint read()
{
    spint x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch - '0');
        ch = getchar();
    }
    return x * f;
}
void print(spint x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
void exgcd(spint A,spint B,spint &x,spint &y){
	if(B==0){
		x=1,y=0;
		return;
	}
	spint xp,yp;
	exgcd(B,A%B,xp,yp);
	x=yp;
	y=xp-(A/B)*yp;
}
int main()
{
    n=read();
    for(spint i=1;i<=n;i++){
    	a[i].m=read();a[i].r=read();
	}cur=n;
	while(cur>=2){
		spint k1,k2,p1,p2,d,r1,r2,l1,l2,m1,m2,lcm,x;
		m1=a[pos].m,r1=a[pos].r;pos++;m2=a[pos].m,r2=a[pos].r;pos++;
		d=__gcd(m1,m2);
//		cout<<"wa!!!\n";print(m1);cout<<" ";print(m2);cout<<"\n";
//		if((r2-r1)%d!=0){cout<<"noooooo!\n";exit(0);}
		exgcd(m1/d,m2/d,l1,l2);
		x=r1+m1/d*l1*(r2-r1);lcm=m1/d*m2;
		a[++n]={x,lcm};cur--;
	}
	spint x=a[pos].r,lcm=a[pos].m;
	print((x%lcm+lcm)%lcm);cout<<"\n";
    return 0;
}
2024/5/23 19:48
加载中...