1.题目描述
东东对幂运算很感兴趣,在学习的过程中东东发现了一些有趣的性质: 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
2.题目解析
从易到难分三种情况分析：
- 以1为底的式子
- 1以外的数为底的式子
- 幂关系
问题
-
(x / y) = (d / c)怎么来的？
从,
分析
用i表示底数，用x,y,b,c表示指数，那么存在关系(i ^ x) ^ c = (i ^ y) ^d。根据幂的指数乘方运算法则x * c = y * d, 问题转换为找到满足(x / y) = (d / c)的个数。 - 为什么要使用
(x/y)=(d/y)?
因为比较容易计算，d/c与x/y经过约分后，最简分数一样。如果x/y是最简分数，那么d/c是x/y的倍数。 -
x,y如何确定？
x,y是i的幂值，可以通过枚举i获得。i^x≤n，i^y≤n，因此可以遍历i的各个幂值。 - 为什么要
y/gcd(x,y)?
因为x/y要约分，使x/y成为最简分数。y/gcd(x,y)是约分后的分母，同样x/gcd(x,y)是约分后的分子。 - 为什么
n要除以y/gcd(x,y)?
当x/y经过约分后，成为最简分数。y/gcd(x,y)是最简分数的分母，n/(y/gcd(x,y))表示n内有多少个最简分母的倍数，也就是有多少组c和d。 - 为什么
*2？因为等号左右交换位置也算一种情况，所以*2。
3.参考答案
#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;
}
