牛牛的幂运算
题目描述
牛牛在做一道数学题,他发现自己不怎么会做,请你帮帮他
求有多少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;
}