题解 | #求幂#

const readline = require("readline")
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
})
let mod = 1000000007
rl.on("line", function (n) {
  // n在1的时候,n*n个
  // n大于1的时候，
  // 1.底数相同的情况下n*(n-1)个
  // 2.底数不同的情况下，a和c，
  /*
    推到为a^b=c^d => (i^x)^b=(i^y)^d ,然后去x,y的最大公约数m,假设x=m*n1,y=m*n2
  */
  let total = (2 * Math.pow(n, 2) - n) % mod

  //let index = 2
  let set = new Set()
  for (let i = 2; i * i <= n; i++) {
    if (set.has(i)) continue
    let temp = i
    let cnt = 0
    while (temp <= n) {
      set.add(temp)
      temp *= i
      cnt++
    }
    for (let x = 1; x <= cnt; x++) {
      for (let y = x + 1; y <= cnt; y++) {
        let res = (parseInt(n / (y / gcd(x, y))) * 2) % mod
        total += res
      }
    }
  }
  console.log(total)
})

function gcd(x, y) {
  return x % y === 0 ? y : gcd(y, x % y)
}

rl.on("close", function () {
  process.exit()
})

(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。