今天比赛的时候拿到的第一道题，其实挺简单的，求两等差序列中相同元素的个数，我想了一下就觉得，只要找到了第一个相等的点，然后后面求最大公约数就可以直接得到结果了
网上叫什么拓展欧几里得，我反正是按照我们的思路来的
关键是如何找到第一个相等的点，因为首项和公差能达到 10^9，项数可以达到10^18，我觉得会不会第一个相等的点就直接爆了long long，不过在跟聪哥统一了一下意见之后，决定试一下，即先暴力找到第一个相等的点。。。
最后WA了。。。因为时间也不多了，而且我担心WA是不是因为我们相等的点已经爆了 unsighed long long 了。。。没想到是我代码写挫了，就是前期找第一个相等的点的时候写挫了。。次奥，这个题没在比赛的时候出了，全部责任在我。，。。。
我前期处理有点乱，其实就写个while(1)循环，唯一出口就是两个相等的时候，我还判断些什么取模是否相等，真是乱，哎
事实证明只要前期处理的好，就基本上没问题了
还有，其实觉得会爆的不如去做一做，最后其实结果可能就是你想的这样
#include <iostream> #include <cstdio> #include <cstring> #define ll unsigned long long using namespace std; struct node { ll n,f,d; }s[2]; ll gcd(ll a,ll b) { if (a<b) swap(a,b); return b==0?a:gcd(b,a%b); } int main() { int t; scanf("%d",&t); while (t--){ scanf("%llu%llu%llu",&s[0].n,&s[0].f,&s[0].d); scanf("%llu%llu%llu",&s[1].n,&s[1].f,&s[1].d); ll sum=0; ll q1=s[0].f,q2=s[1].f; while (1){ //前期处理得到第一个相等的数 if (q1==q2){sum=q1;break;} if (q1<q2){ ll tmp=(q2-q1)/s[0].d; if (tmp==0) tmp=1; q1+=tmp*s[0].d; if (q1<q2) q1+=s[0].d; } else{ ll tmp=(q1-q2)/s[1].d; if (tmp==0) tmp=1; q2+=tmp*s[1].d; if (q2<q1) q2+=s[1].d; } } ll ans; ll num=gcd(s[0].d,s[1].d); //后期比较得到最多的相同的元素，最后要用min比较而不是max是因为要找到满足两个序列都有的最多的元素，不是单独一个序列最多就可以的 ll dis=(sum-s[0].f)/s[0].d+1; dis=s[0].n-dis; ans=dis/(s[1].d/num)+1; dis=(sum-s[1].f)/s[1].d+1; dis=s[1].n-dis; ans=min(ans,(dis/(s[0].d/num))+1); printf("%llu ",ans); } return 0; }