牛客P21578 思维，数论

题意：

给定$n$，求有多少四元组$(a,b,c,d)$满足$a^b=c^d$

Solution：

从唯一分解看，幂$b,d$只改变质因数的幂，而不改变质因数的种数，因此，要满足题意，$a,c$一定存在结构一样的部分，设为$x$，那么
$$\begin{gathered} a=x^{k_1} \\ c=x^{k_2} \end{gathered}$$

• 对$x=1$，$b,d$不一定一样，且都任意取值，方案数为$n^2$，此时为$a=c=1$；

• 对$a=c\ne 1$时，$a=c\in [2,n]$，$b=d\in [1,n]$，方案数为$n(n-1)$

• 下面只需要考虑$a\ne c$的情况

  当我们知道同样部分$x$的时候，我们很容易可以知道以这个数为最小结构的数有多少，而我们只需要枚举一个最小的$x$，就可以统计所有以$x$为最小结构的数，他们分别是
  $$x,x^2,x^3,....$$
  此时只需要找出序列长度大于$2$的$x$，即$x^2\le n\Rightarrow x\le \sqrt{n}$，我们用$O(\sqrt{n})$枚举$x$，只需要找出最大的$i$满足$x^i\le n$，即可找出这些数，那么$a,c$一定出现在这些数之中，原题要满足
  $$x^{b{k}_1}=x^{d{k}_2}\Rightarrow b{k}_1=d{k}_2$$

  由于$n\le 10^9$，因为$2^{32}>10^9$，于是$i\le 32$，所以考虑枚举$k_1,k_2$，由于$a\ne c$，即$k_1\ne k_2$，此时方程解的组数就是方案数，先化简方程至$gcd(k_1,k_2)=1$，即解
  $$\frac{b}{d}=\frac{k_2}{k_1}$$
  设$b=k_{2}x\le n,d=k_{1}x\le n$，有 x ≤ m i n { n k 1 , n k 2 } x\leq min\{\frac{n}{k_{1}},\frac{n}{k_{2}}\} x≤min{k1​n​,k2​n​}，

  如果不化简，这个$x$可能不是最大的

  最后，这个序列的元素的都用最小的$x$统计了，所以$x$的其他幂需要跳过，数组记录即可

// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=1e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e9+7;

ll n,ans;
bool vis[N];

int main()
{
    cin>>n; ans=(1ll*n*n%mod+1ll*n*(n-1)%mod)%mod;
    int limit=sqrt(n);
    for(int i=2;i<=limit;i++)
    {
        if(vis[i]) continue;
        ll max1=1,now=i;
        while(now*i<=n) max1++,now*=i;
        now=i;
        for(int j=1;j<=max1;j++)
        {
            if(now<=limit) vis[now]=true;
            for(int k=1;k<=max1;k++)
                if(j!=k) ans=(ans+n/max(j/__gcd(j,k),k/__gcd(j,k)))%mod;
            now*=i;
        }
    }
    cout<<ans;
    return 0;
}
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
37
38
39