Flintx

2018京东校招题 求幂

题意

给定 $n$ ,求有多少个四元组 $a,b,c,d$ 满足 $a^b = c^d,1 \leq a,b,c,d \leq n, n \leq 10^5$

思路

$a^b = c^d$ 等式成立分两种情况:

  • $a^b = a^b$ ,即自身等于自身;
  • $(i^x)^c = (i^y)^d,xc=yd\leq n$ .

关于第一种情况,显然存在 $n^2$ 个这样的等式,因为 $a, b$ 均有 $n$ 种情况。

关于第二种情况,可以先枚举 $(x,y)$ 二元组,当 $(x,y)$ 确定时,二元组 $(c,d)$ 的就只有

种可能情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int gcd(int a, int b)
{
return b == 0? a : gcd(b, a % b);
}
int main()
{
int n;
while (cin >> n && n) {
set<int> s;
int sqn = (int)sqrt(n + 0.5);
long long ans = (1LL * n * (2 * n - 1)) % MOD;
for (int i = 2; i <= sqn; i++) {
if (s.find(i) != s.end()) continue;
int cnt = 0;
long long tmp = i;
while (tmp <= n) {
s.insert(tmp);
tmp *= i;
cnt++;
}
for (int x = 1; x <= cnt; x++) {
for (int y = x + 1; y <= cnt; y++) {
ans += (n / (y / gcd(x, y))) * 2LL;
ans %= MOD;
}
}
}
cout << ans % MOD << endl;
}
return 0;
}

还有一些题有时间可以看下:

  • 招商银行的博弈题,数据很弱,但是正解不好找啊。
  • 网易