本文共计713个文字，预计阅读时间需要3分钟。

问题：对于一对数（a，b），如果满足a^b > b^a，则称这个数为好的数。例如，如果a^2 > 2^a，那么这对数是好的数。问题：对于一对数（a，b），如果满足a/b > b/a，那么这对数是好的数。

problem对于一个数对(a,b)如果满足a%bab则称这个数对为“好的数对”。如果a⩽n,b⩽n那么有多少对数对是“好的数对”

problem

对于一个数对(a,b) 如果满足a%ba/b则称这个数对为“好的数对”。 如果 a⩽n,b⩽n那么有多少对数对是“好的数对”呢

1⩽n⩽1e9

pdf题面

Sample Input

5

8

3

65

Sample Output

3

7

1

131

思路1

表面意思 ∑na1∑nb1[a%ba/b] 这里a/b⌊ab⌋

由于aab∗ba%b 可得a(a%b)∗(b1) 那我只要枚举a和它的因子d,凡是满足a=(a%(d−1))∗d 的因子d，d−1即为对应的b。时间复杂度O(nlogn)会TLE

令ta%b 显然t

。对于每一个t累加b的个数nt−1−t即为答案。时间复杂度O(n)会TLE。