[53]求幂-京东2018秋

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为底的式子
2. 1以外的数为底的式子
3. 幂关系

问题

1. (x / y) = (d / c)怎么来的？
   从,分析
   
   
   用i表示底数，用x,y,b,c表示指数，那么存在关系(i ^ x) ^ c = (i ^ y) ^d。根据幂的指数乘方运算法则x * c = y * d, 问题转换为找到满足(x / y) = (d / c)的个数。
2. 为什么要使用(x/y)=(d/y)?
   因为比较容易计算，d/c与x/y经过约分后，最简分数一样。如果x/y是最简分数，那么d/c是x/y的倍数。
3. x,y如何确定？
   x,y是i的幂值，可以通过枚举i获得。i^x≤n，i^y≤n，因此可以遍历i的各个幂值。
4. 为什么要y/gcd(x,y)?
   因为x/y要约分，使x/y成为最简分数。y/gcd(x,y)是约分后的分母，同样x/gcd(x,y)是约分后的分子。
5. 为什么n要除以y/gcd(x,y)?
   当x/y经过约分后，成为最简分数。y/gcd(x,y)是最简分数的分母，n/(y/gcd(x,y))表示n内有多少个最简分母的倍数，也就是有多少组c和d。
6. 为什么*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;
}

牛客题目