pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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;
}