数论题还是好恶心啊。

题目大意：给你两个不超过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
      
       #define ll long longusing namespace std;ll a,b,ans=0;vector
       
         va;void work(ll y)// y值表示目前 b的值为 gcd（a，b）的y倍。{    if(y==0) return;    ll k=y;    for(int i=0;i
        
          vb;    for(int i=0;i
         
          >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