题意:
a=A*gcd(a,b) b=B*gcd(a,b)
一次递归后,变成了 f(A*gcd(a,b),(B-1)*gcd(a,b))
若 gcd(A,(B-1))=1, 那么 这一层递归的 gcd(a,b)仍等于上一层递归的 gcd(a,b)
也就是说,b-gcd(a,b),有大量的时间减的 gcd(a,b)相同,
若计算出减了 S 次相同的 gcd(a,b)
那就可以直接由 f(a,b)到 f(a,b-S*gcd(a,b))+ S
设 T 是 A 的任意因子
那么 S 满足 (B-S)%T=0,且 S 最小
移项得 S=B%T
即 S 是 B 对 A 的所有因子取模得到的数中最小的那个
新的一次递归中,
a '=a,b' =(B-S)*gcd(a,b),gcd ' = gcd*T
如何得到 T 和 S?
枚举所有因子会 TLE
我们发现,整个过程 a 始终没有改变,只是参与了求 gcd
对于输入的 a,b
令 A=a/gcd(a,b),B=b/gcd(a,b)
这样 A,B 就没有公因子
这样 原来的 b-S*gcd 相当于 现在的 B-S
求出 A 的所有素因子
因为 A 为定值,所以下一次求 S 用 A 的素因子时,可以从上一次求 S 用的 A 的素因子剩下的里选
就是说
如果这次某个因子是 B 的因子,那么下一次就不会用这个因子了,B/= 这个因子
即这个因子参与构成新的 gcd
如果这次某个因子不是 B 的因子,下一次就可以考虑它
- #include < vector > #include < iostream > using namespace std;
- typedef long long LL;
- LL ans;
- vector < LL > p;
- vector < LL > ::iterator it;
- LL gcd(LL a, LL b) {
- return ! b ? a: gcd(b, a % b);
- }
- void work(LL y) {
- if (!y) return;
- LL k = y;
- for (it = p.begin(); it != p.end(); ++it) k = min(k, y % ( * it));
- ans += k;
- y -= k;
- vector < LL > q;
- for (it = p.begin(); it != p.end(); ++it) if (y % ( * it)) q.push_back( * it);
- else y /= ( * it);
- swap(p, q);
- work(y);
- }
- int main() {
- LL a,
- b;
- cin >> a >> b;
- LL g = gcd(a, b);
- a /= g;
- b /= g;
- for (LL i = 2; i * i <= a; i++) while (a % i == 0) {
- p.push_back(i);
- a /= i;
- }
- if (a > 1) p.push_back(a);
- work(b);
- cout << ans;
- }
E. Vasya's Function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Vasya is studying number theory. He has denoted a function
f(a, b) such that:
Vasya has two numbers x and y, and he wants to calculate f(x, y). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.
Input
The first line contains two integer numbers
x and y (1 ≤ x, y ≤ 1012).
Output
f(x, y).
Examples
input
3 5
output
- 3
input
6 3
output
1
来源: http://www.bubuko.com/infodetail-2451862.html