东东对幂运算很感兴趣,在学习的过程中东东发现了一些有趣的性质: 9^3 = 27^2, 2^10 = 32^2
东东对这个性质充满了好奇,东东现在给出一个整数n,希望你能帮助他求出满足 a^b = c^d(1 ≤ a,b,c,d ≤ n)的式子有多少个。
例如当n = 2: 1^1=1^1
1^1=1^2
1^2=1^1
1^2=1^2
2^1=2^1
2^2=2^2
一共有6个满足要求的式子
输入包括一个整数n(1 ≤ n ≤ 10^6)
输出一个整数,表示满足要求的式子个数。因为答案可能很大,输出对1000000007求模的结果
2
6
#include <bits/stdc++.h> using namespace std; const int mod=1e9+7; int main() { int n; scanf("%d",&n); set<int> S; int res=1LL*n*(n*2-1)%mod; for(int i=2;i*i<=n; ++i) { if(S.find(i)!=S.end()) continue; // 如果已经存在则跳过 long long temp=i; int cnt=0; while(temp<=n) { // 求小于n的最大幂 S.insert(temp); temp=temp*i; cnt++; } for(int x=1; x<=cnt; ++x){ // 遍历统计到的幂 for(int y=x+1; y<=cnt; ++y){ res=(res+n/(y/__gcd(x,y))*2LL)%mod; } } } printf("%d\n",res); return 0; }