本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-11 19:31:12

题目传送门：Codeforces

Luogu

题意

给你一个矩阵，第 $i$ 行第 $j$ 列写着 $i^j$，问矩阵中有多少不同的数。

思路

首先我们可以发现，出现了多少数与指数密切相关，那么考虑第 $d$ 行，我们令 $d$ 在之前都没有出现过（$d \neq 1$），那么我们可以将第 $d$ 行，第 $d^2$ 行，第 $d^3$ 行一直到最大的小于 $n$ 的第 $d^k$ 行单独提取出来看，我们发现出现的数的数量只取决于指数，而且发现提取出来的矩阵的第 $i$ 行第 $j$ 列的数的指数为 $i \times j$。

综合考虑，我们还发现，这个规律对于任何的底数都成立，于是在统计答案时把当前统计到的行打标记，在下一次遍历到的时候避免重复统计即可。

对于提取出来的矩阵，我们发现最多只有 $\log_{2}{n}$ 行，既然对于每个底数答案不变，那么我们可以预处理出来对于提取出来的前 $i$ 行的答案。

复杂度 $O(n \log n)$。

不理解可以结合代码食用。

代码

#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
int n,m;
int sum;
bool vis[N],us[N*20];\/\/vis: 这一行有没有被统计过 ; us:这个指数有没有出现过 
int cnt[40];\/\/前i行的答案 
int ans=1;\/\/第一行不用统计,直接是1 
signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=20;i++)
	{
	    for(int j=1;j<=m;j++)
        {
            if(!us[i*j]) 
            {
                sum++;   \/\/sum从0开始,统计前i行的答案 
                us[i*j]=1;
            }
        }
        cnt[i]=sum;
    }
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])  \/\/如果这一行没被统计过,那么统计 
        {
            int p=i;
            int cur=0;
            while(p<=n)
            {
                cur++;
                vis[p]=1;
                p*=i;
            }
            ans+=cnt[cur];
        }
    }
    cout<<ans;
    return 0;
}