首页 > 代码库 > Educational Codeforces Round 26 E - Vasya's Function

Educational Codeforces Round 26 E - Vasya's Function

2024-11-20 04:03:01   203人阅读

数论题还是好恶心啊。

题目大意：给你两个不超过1e12的数 x,y，定义一个f ( x, y ) 如果y==0 返回 0 否则返回1+ f ( x , y - gcd( x , y ) );

 

思路：我们设gcd ( x , y) 为G，那么 设 x  = A*G，y = B*G，我们考虑减去多少个G时x y 的gcd会改变，我们设减去

k个G的时候 x和y 的gcd为改变，即 A*G 和 ( B - k ) * G 的 gcd 改变了，什么情况下会改变呢，就是A 和( B -  k )的gcd

不为 1 ，这样我们就不断地找出 k 就能得出答案。那么现在问题变成了怎么快速地求出 k ，我们设 A 中的某个因子为

r，则( B - k )%r == 0 , 设( B - k ) / r的商为 q ，则 B - k = q * r  变形一下变成，B = k + q * r ，两边对 r  取余，B % r = k

这样我们就能用 B 和 A中的质因数求出 k ，那么我们每次需要记录的就是，B 是 A和B的gcd 的多少倍就，以及A的没有被

用过的质因数。

技术分享 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,ans=0;
vector<ll> va;
void work(ll y)// y值表示目前 b的值为 gcd（a，b）的y倍。
{
    if(y==0) return;
    ll k=y;
    for(int i=0;i<va.size();i++)
    {
        k=min(k,y%va[i]);
    }
    ans+=k;y-=k;
    vector<ll> vb;
    for(int i=0;i<va.size();i++)
    {
        if(y%va[i]==0) y/=va[i];
        else vb.push_back(va[i]);//没有用过的a的质因数。
    }
    va=vb;
    work(y);
}
int main()
{
    cin>>a>>b;
    ll gcd=__gcd(a,b);
    a/=gcd;b/=gcd;//保证了a和b没有公共的因子。
    for(ll i=2;i*i<=a;i++)
    {
        while(a%i==0)
        {
            va.push_back(i);
            a/=i;
        }
    }
    if(a>1) va.push_back(a);
    for(int i=0;i<va.size();i++) printf("%d ",va[i]);
    work(b);
    cout<<ans<<endl;
    return 0;
}
View Code

 

Educational Codeforces Round 26 E - Vasya's Function


联系
我们