Codeforces 837E Vasya's Function 数论找规律

题意：定义F（a，0） = 0，F（a，b） = 1 + F（a，b - GCD（a，b）。给定 x 和 y （<=1e12）求F（x，y）。

题解：a=A*GCD（a，b） b=B*GCD（a，b），那么b-GCD（a，b） = （B-1）*GCD（a，b），如果此时A和B-1依然互质，那么GCD不变下一次还是要执行b-GCD（a，b）。那么GCD什么时候才会变化呢？就是说找到一个最小的S，使得（B-S）%T=0其中T是a的任意一个因子。变形得到：B%T=S于是我们知道S=min（B%T）。也就是说b剪掉了S次相同的一个GCD之后，ab有了新的GCD。新的GCD等于原来的GCD*T，可以把a、b都/T，同时GCD*T，这样问题化归为上述同样的问题，进行迭代

当B和A公约数不为1的时候（开始的时候，或者B减了一定次数1的时候），就相当于A和B同除以gcd(A,B)，然后B继续一次减1。

这样只要每次计算出每次B要减多少次1才能和A有不为1的公约数。

那么预处理出A的质因数，然后每次对A的质因数判断一下，哪个最近（也就是模最小）即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {

    LL x, y;

    cin >> x >> y;

    LL g = __gcd(x, y);

    x /= g, y /= g;

    vector<LL> a;

    for (LL i = ; i * i <= x; ++ i) {

        while (x % i == ) {

            x /= i;

            a.push_back(i);

        }

    }

    if (x > ) a.push_back(x);

    LL ans = ;

    while (y) {

        LL g = y;

        for (LL i : a) {

            g = min(g, y % i);

        }

        ans += g;

        y -= g;

        vector<LL> b;

        for (LL i : a) {

            if (y % i == ) {

                y /= i;

            }

            else {

                b.push_back(i);

            }

        }

        a.swap(b);

    }

    cout << ans << endl;

}

巴特西

Codeforces 837E Vasya's Function 数论找规律

最新文章

热门文章

巴特西

Codeforces 837E Vasya's Function 数论 找规律

最新文章

热门文章

Codeforces 837E Vasya's Function 数论找规律