Educational Codeforces Round 26: E. Vasya's Function
http://codeforces.com/contest/837/problem/E
解法
b-gcd(a,b) は gcd(a,b) の倍数である。つまり次の操作でも gcd は gcd(a,b) の倍数になるはずである。何だかんだでf(a,b)=f(a/g,b/g)
が成り立つ。よってf(a,b)の計算は
- a,bをgcd(a,b)で割る
- gcd(a,b)≠1 になるまでbを引き続ける
の繰り返しでできる。前者が起きる回数は O(log a) であるから、もし後者を高速にシミュレーションできれば解くことができる。
後者はあらかじめ a の素因数リストを計算しておけば分かる。
#include <iostream> #include <algorithm> #include <vector> using namespace std; long long gcd(long long a, long long b) { while (b!=0) { long long tmp=a; a=b; b=tmp%b; } return a; } vector<long long> primes(long long n) { vector<long long> ret; for (long long i=2; i*i<=n; i++) { if (n%i==0){ ret.push_back(i); while (n%i==0) n/=i; } } if (n!=1) ret.push_back(n); return ret; } int main() { long long a, b; cin>>a>>b; auto ps=primes(a); long long ans=0; while (b!=0) { long long g=gcd(a, b); a/=g; b/=g; long long next=0; for (long long p:ps) if (a%p==0) { next=max(next, (b-1)/p*p); } ans+=b-next; b=next; } cout<<ans<<endl; }