时间复杂度 $\mathcal{O}(T\log^2 v)$。

#include <bits/stdc++.h>
#define ll long long 
#define ldb long double
using namespace std;

const double eps=1e-9;
const int Mod=1e9+7;

int T;
ll A,B,C;
ll ans;

int ggcd[100][100],f[100];
vector<int>prm;
bitset<100>isp;

int main(){

    for(int i=1;i<=70;i++)
        for(int j=1;j<=70;j++)
            ggcd[i][j]=__gcd(i,j);
    for(int i=2;i<=70;i++){
        if(!isp.test(i)) prm.emplace_back(i);
        for(int j=i+i;j<=70;j+=i) isp.set(j);
    }
        
    for(int i=1;i<=70;i++){
        f[i]=1;
        for(auto j:prm) if(!(i%j)) f[i]*=j;
    }

    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld",&A,&B,&C);
        ans=0;                  
        for(int a=1;a<=32;a++){ 
            for(int b=1;b<=60;b++){
                if(ggcd[a][b]>1) continue;
                ll c=min(min(pow<ldb>((double)C*a/b,1./a)+eps,pow<ldb>(A,1./a)+eps),pow<ldb>(B,1./b)+eps);
                c=c/f[a]-(a==1);
                if(c>0) ans=(ans+c)%Mod;
            }
        }
        printf("%lld\n",(ans+C)%Mod);
    }

    system("pause");
    return 0;
}
/*
3
1 2 3
3 4 5 
6 7 8

2
1000000000000000000 1000000000000000000 1000000000000000000
114514191981011451 114514191981011452 114514191981011453
*/