B. 幂运算

单点时限: 1.0 sec

内存限制: 256 MB

QQ小方以前不会幂的运算，现在他会了，所以他急切的想教会你。

对于形如 xa 的计算，可以归结到乘法运算 xa=∏a1x 。

单单讲给你听肯定是不够的，为了表现自己，QQ小方现在要考考你。

QQ小方现在想知道有多少四元组 (a,b,c,d) （ 1≤a,b,c,d,a≤amax,b≤bmax,c≤cmax,d≤dmax ）满足 ab=cd ，答案对 109+7 取模。

输入格式

输入数据第一行包含一个整数 T(1≤T≤100) ，表示数据组数。

每组数据包含一行， 四个整数 amax,bmax,cmax,dmax （ 1≤amax,bmax,cmax,dmax≤109 ），含义如题目所述。

输出格式

对于每一组数据，输出一行包含一个整数表示答案，答案对 109+7 取模。

样例

Input

2
2 3 4 5
10 10 10 10

Output

19
222

这一道题我和队友以前就在牛客看到类似题了，历时几个月，终于明白了解法（╥_╥)

解法：

a=c,b=d 或者 a=b=1 是很容易统计的，无论如何都符合等式。

首先 ab,cd 从素因数分解看，每个素因子系数都要是相同的才能相等。得出如果 a≠b  a,b>1⇒a=xkk,b=xk,(1≤kk,k≤32) 即底数的素因子结构必须是相同的。然后就是 gcd(kk,k)=1 否则会产生重复计数的情况。这里枚举 kk,k 就行了，这样枚举的情况就是 a=xkk,b=b′,c=xk,d=d′,xkkb′=xkd′ 。剩下的就是根据输入的四个数确定 x(xkk≤amax,xk≤bmax),b′,d′(b′⋅kk=d′⋅k) 复杂度应该是 O(322logn)


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod1=(1000000000+7);
ll a,b,c,d;
ll qm(ll x,ll y){
	ll ans=1;
	if(x==1)return 1;
	while(y){
		if(y&1){
			ans*=x;
		}
		y>>=1;
		x=x*x;
	}
	return ans;
}
ll gcd(ll x,ll y){
	return y?gcd(y,x%y):x;
}
void solve(){
	ll ans=0;ans=b*d;
	for(int i=1;i<32;i++){
		for(int j=1;j<32;j++){
			if(gcd(i,j)!=1)continue;
			int A=pow(a,1.0/i);int C=pow(c,1.0/j);
			for(;qm(A,i)<=a;A++);
			for(;qm(C,j)<=c;C++);
			A--;C--;
			//ans=(ans+min(A-1,C-1)*min(b/j,d/i)%mod)%mod;
            (ans+=(min(A-1,C-1)*min(b/j,d/i))) %= mod1;
		}
	}
	cout<<ans<<endl;
}
int main(){
	int t;cin>>t;
	while(t--){
		cin>>a>>b>>c>>d;
		solve();
	}
	return 0;
}