数论-欧几里得最大公约数- same gcd

​ 给定a,b，问有多少个x(0<=x 思路

d = g c d ( a , b ) = g c d ( a + x , b ) → 1 = g c d ( a + x d , b d ) d=gcd(a,b)=gcd(a+x,b)to 1=gcd(frac{a+x}{d},frac{b}{d}) d=gcd(a,b)=gcd(a+x,b)→1=gcd(da+x​,db​)

a + x d ∈ [ a d , a d + b d ) frac{a+x}{d}in[frac{a}{d},frac{a}{d}+frac{b}{d}) da+x​∈[da​,da​+db​)

题目转化成，求在上述范围内与b/d互质的个数，进而转化成求b/d的欧拉函数
e u l e r s [ 1 , b d ) ≡ e u l e r s [ a d , a d + b d ) eulers[1,frac{b}{d})equiv eulers[frac{a}{d},frac{a}{d}+frac{b}{d}) eulers[1,db​)≡eulers[da​,da​+db​)

#include 

using namespace std;
typedef long long LL;

LL gcd(LL a, LL b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

LL phi(LL x){
    LL res=x;
    for(int i=2;i<=x/i;i++){
        if(x%i==0)res=res/i*(i-1);
        while(x%i==0)x/=i;
    }
    if(x!=1)res=res/x*(x-1);
    
    return res;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        LL a,b;//注意数据范围
        cin>>a>>b;
        cout<