题目描述

牛牛在做一道数学题，他发现自己不怎么会做，请你帮帮他
求有多少a,b,c,d满足a^b = c^d， 1<=a,b,c,d<=n, 模 10^9+7

输入描述:

输入一个整数n (1 ≤ n ≤ 109)

输出描述:

输出一个整数

示例1

输入

复制

2

输出

复制

6

示例2

输入

复制

100

输出

复制

21620

示例3

输入

复制

22306

输出

复制

68467

备注:

子任务一30分：n<=10000
子任务二30分：n<=1000000
子任务三40分：n<=1000000000

自从几个月之前我和队友在牛客看到并试图做出这道题，我们在当天失败后，问了n个人，用了n多种方法，依然不知道怎么做，还好华东师范月赛也出到一个基本差不多的题，通过代码和题解，我终于知道了做法(╥_╥)

由于华东师范不是输入n，而是输入amax，bmax，cmax，dmax，只要把题解的（abcd）max都换成n就可以了

代码


#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 n;
    while(scanf("%d",&n)!=EOF)
    {
        a=b=c=d=n;
        solve();
    }
	return 0;
}