CF1646E Power Board

刘梓轩2010 · 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;
}