题解 | #牛牛的幂运算#

题意：

求有多少方案使得 $a,b,c,da,b,c,d$ 满足 $a^b=c^{d}a^b=c^d$， $1\le a,b,c,d\le n1\backslash leq\; a,b,c,d\; \backslash leq\; n$，结果对 $10^9+710^9+7$ 取模

分析：

可以将 $a,ca,c$ 的取值分为以下三种情况：

• $a=c=1a=c=1$ ,很显然此时 $b,db,d$ 可以取 $[1,n][1,n]$ 内的任意值，故方案数为 $n^{2}n^2$
• $a=c\mathrm{\ne }1a=c\backslash neq\; 1$,此时 $b,db,d$ 取值必须相等，故方案数为 $n\ast (n-1)n*(n-1)$
• $a\mathrm{\ne }ca\; \backslash neq\; c$, 我们从2到 $\sqrt{n}\backslash sqrt\{n\}$ 枚举a，求出满足 $a^b=c^{d}a^b=c^d$ 的 $abcdabcd$，对于每个a要遍历b,d，计算出来的方案要乘以2，因为ac位置可以调换，每次遍历是log级别的，然后再将a的次方全部打上记号，后面枚举到就无需计算了。为什么是枚举到 $\sqrt{n}\backslash sqrt\{n\}$ ？因为当 $a>\sqrt{n}a\; >\; \backslash sqrt\{n\}$，c不可能大于a了，a=c的情况在第二种情况已经计算过，a>c的情况在前面枚举a时计算过了。

最后，再将三种情况的方案数相加。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res *= a;
		a *= a;
		b >>= 1;
	}
	return res;
}
ll n;
ll range;
int f[100010];
ll gcd(ll x, ll y) {
	return y == 0 ? x : gcd(y, x % y);
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
void solve() {
	cin >> n;
	range = sqrt(n);
	ll ans = 0;
	for (ll i = 2; i <= range; i++) {
		if (f[i] == 0) {
			for (ll j = 1; 1; j++) {
				ll tmp = qpow(i, j);
				if (tmp <= range) {
					f[tmp] = 1;
				}
				if (tmp > n) break;
				for (ll k = 1; k < j; k++) {
					ans += n / (lcm(j, k) / min(j, k)) * 2;
					ans %= mod;
				}
			}
		}
	}

	cout << (ans + (n - 1) * n % mod + n * n % mod) % mod << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
	}
	return 0;
}