UVALive 6763 / CSU 1446

今天比赛的时候拿到的第一道题，其实挺简单的，求两等差序列中相同元素的个数，我想了一下就觉得，只要找到了第一个相等的点，然后后面求最大公约数就可以直接得到结果了

网上叫什么拓展欧几里得，我反正是按照我们的思路来的

关键是如何找到第一个相等的点，因为首项和公差能达到 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[];

ll gcd(ll a,ll b)

{

    if (a<b) swap(a,b);

    return b==?a:gcd(b,a%b);

}

int main()

{

    int t;

    scanf("%d",&t);

    while (t--){

        scanf("%llu%llu%llu",&s[].n,&s[].f,&s[].d);

        scanf("%llu%llu%llu",&s[].n,&s[].f,&s[].d);

        ll sum=;

        ll q1=s[].f,q2=s[].f;

        while (){ //前期处理得到第一个相等的数

            if (q1==q2){sum=q1;break;}

            if (q1<q2){

                ll tmp=(q2-q1)/s[].d;

                if (tmp==) tmp=;

                q1+=tmp*s[].d;

                if (q1<q2) q1+=s[].d;

            }

            else{

                ll tmp=(q1-q2)/s[].d;

                if (tmp==) tmp=;

                q2+=tmp*s[].d;

                if (q2<q1) q2+=s[].d;

            }

        }

        ll ans;

        ll num=gcd(s[].d,s[].d); //后期比较得到最多的相同的元素，最后要用min比较而不是max是因为要找到满足两个序列都有的最多的元素，不是单独一个序列最多就可以的

        ll dis=(sum-s[].f)/s[].d+;

        dis=s[].n-dis;

        ans=dis/(s[].d/num)+;

        dis=(sum-s[].f)/s[].d+;

        dis=s[].n-dis;

        ans=min(ans,(dis/(s[].d/num))+);

        printf("%llu\n",ans);

    }

    return ;

}

巴特西

UVALive 6763 / CSU 1446

最新文章

热门文章