首页 > 代码库 > UVALive 6763 / CSU 1446

UVALive 6763 / CSU 1446

2024-07-05 00:26:49   224人阅读

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

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

关键是如何找到第一个相等的点，因为首项和公差能达到 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\n",ans);
    }
    return 0;
}

 


联系
我们