首页 > 其他分享 >CF1646E Power Board 题解

CF1646E Power Board 题解

时间:2023-04-17 18:13:54浏览次数:56  
标签:CF1646E le log cdot 题解 int Board 次方 ldots

题目链接:https://codeforces.com/contest/1646/problem/E

题目大意:

有一个 \(n \times m\) 的矩阵,其中第 \(i\) 行第 \(j\) 列的格子中的数字是 \(i^j\)。
问:矩阵中存在多少个不同的数?

解题思路:

可以很明显地发现,第 \(1\) 行的数字全部都是 \(1\),而且在其它行不会出现数值为 \(1\) 的数字。

我们称一个整数是 次方数 如果它它可以表示成 \(x^a\) 的形式,其中 \(x\) 和 \(a\) 都是正整数且 \(a \gt 1\)。对于一个不是次方数的正整数 \(x\),我们定义 \(R(x)\) 表示整数 \(x, x^2, x^3, \ldots\) 的出现在矩阵中的数字对应的集合。

可以断言:如果存在两个整数 \(x\) 和 \(y\) 满足 \(x \neq y\) 且 \(x\) 和 \(y\) 均不是次方数,则 \(R(x)\) 和 \(R(y)\) 不包含相同的元素。
证明:假设存在相同的元素,那么也就说明存在两个正整数 \(a, b\) 满足 \(x^a = y^b\),这等价于 \(x = y^{\frac{b}{a}}\),由于 \(y\) 不是一个次方数,所以 \(\frac{b}{a}\) 不是一个整数。如果 \(\frac{b}{a} = 1\) 则 \(x = y\),这也不可能发生。而 \(\frac{b}{a} \gt 1\) 也不可能发生,因为 \(x\) 不是一个次方数。所以:不会存在相同的元素。

基于上述结论,对于每一个非次方数 \(x\),我们可以单独计算 \(R(x)\)。

对于一个整数 \(x\),我们用 \(k\) 表示以 \(x\) 的幂开头的行数。则 \(R(x)\) 包含了所有满足 \(1 \le i \le k\) 且 \(1 \le j \le m\) 的 \(x^{i \cdot j}\)。然后,集合的大小就等价于存在多少个不同的 \(i \cdot j\) 满足 \(1 \le i \le k\) 且 \(1 \le j \le m\)。这也就是说,集合中的数字个数与 \(x\) 无关,而只与 \(k\) 有关。

因此,\(R(x)\) 的大小取决于 \(k\)。因为 \(x^k \le n\),所以我们可以得到 \(k \le \log(n)\)。因为,对于每一个 \(k = 1, 2, \ldots, \lfloor \log(n) \rfloor\),我们只需去计算一下存在多少个不同的整数 \(i \cdot j\) 满足 \(1 \le i \le k\) 且 \(1 \le j \le m\) 即可。我们可以使用一个长度为 \(m \cdot \log(n)\) 的数组,在第 \(i\) 步(对于 \(i = 1, 2, \ldots, \lfloor \log(n) \rfloor\))我们标记数字 \(i, 2i, \ldots, mi\) 在数组中是访问过的,并且将没有访问过的标记为访问过然后加入到数组中即可。在第 \(i\) 步我们相当于计算了 \(k = i\) 的情况。

示例程序:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

bool vis[maxn * 20], vis2[maxn];
int n, m, cnt, sum[maxn];
long long ans;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= m; j++) {
            if (!vis[i * j]) {
                vis[i * j] = true;
                cnt++;
            }
        }
        sum[i] = cnt;
    }
    ans = 1;
    for (int i = 2; i <= n; i++) {
        if (vis2[i]) continue;
        long long x = i, k = 0;
        while (x <= n) {
            vis2[x] = true;
            k++;
            x *= i;
        }
        ans += sum[k];
    }
    cout << ans << endl;
    return 0;
}

标签:CF1646E,le,log,cdot,题解,int,Board,次方,ldots
From: https://www.cnblogs.com/quanjun/p/17326684.html

相关文章

  • idea中tomcat中文显示乱码问题解决
    组合拳:1、找到tomcat安装目录下面的logging.properties文件如下图:2、修改java.util.logging.ConsoleHandler.encoding=utf-8为java.util.logging.ConsoleHandler.encoding=UTF-8 3、打开idea,在file->settings->appearence里修改Name的值为支持中文的字体4、修改file......
  • 洛谷P7492 [传智杯 #3 决赛] 序列 题解 数列分块
    题目链接:https://www.luogu.com.cn/problem/P7492解题思路:分块。解题思路全部来自yzy1大佬的博客额外掌握技能:编译时加入-Wall参数。示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+5;intn,m,blo,//n表示数列长度,m表......
  • abc250_d 250-like Number 题解
    250-likeNumber题意给定一个整数\(n\),求有多少小于等于\(n\)的满足以下条件的整数\(k\):\(k\)可以被表示为\(k=p\timesq^3\),其中\(p\ltq\),并且\(p,q\)均为质数。数据范围\(1\leqslantn\leqslant10^{18}\),\(n\)是整数。思路首先,我们发现这个式子中......
  • AT_agc003_e 题解
    题目链接神仙题,我会把我自己思考的过程一步步写出来。初看这题时感觉没什么思路,所以随便算了点东西。很容易发现如果对于一个$i$,$q_i\geqq_{i+1}$,那么$q_i$就没有意义,每次把元素放进来时先把头部比它大的都弹走,再把它放进去,设处理完的size为cnt。然后就是这道题的精髓所......
  • Atcoder题解:Agc002_f
    我们可以把这个理解成一种类似卡塔兰数的形式,我们发现,被安排的\(0\)球总数\(i\)和已经出现的颜色种数\(j\)在任意时刻都必须满足\(i\gej\)。然后就可以\(dp\)了,我们每次钦定下一个转移的球是某种颜色。如果下一个转移的球不是\(0\),那么我们就一次性把后面所有这种颜色......
  • Atcoder题解:Agc004_e
    \[吓死我了,还以为写了半天的被自己删掉了\]\[但是\text{Ctrl+S}会保存草稿啊\]\[以后一定要保留这个好习惯\]第一步转化题意,我们把“所有机器人移动”转化成“出口带着边框移动”,而在出口运动过程中超出边框的机器人,就“死”了。然后我们发现,出口运动过程中,假设出口目前走到......
  • js 传递汉字 乱码_JavaScript 字符串反转乱码问题解决
    https://blog.csdn.net/weixin_36483301/article/details/113451892emoji表情和非常用字实际解决中文编码问题,可以通过解码解决js中使用decodeURL即可解决......
  • Atcoder题解:Agc013_e
    我们考虑转化题意,一个合法的将\(1\simN\)划分成长度依次为\(a_1,a_2,\cdotsa_k\)的小区间,对答案的贡献为\(a_1^2a_2^2\cdotsa_k^2\)。化贡献为方案数,我们在每个长度为\(a_i\)的小区间内放置两个独立的标记,每个合法的划分方案对放置标记方案种数的贡献恰好是其对最终答......
  • CF题解
    D.ABGraph2000构造https://codeforces.com/problemset/problem/1481/D题解:由于只有两种边,我们可以枚举较小结构的特性并循环来构造整体解。对于任意两个点,[u->v,v->u]只有4种情况,对于[1,1],[0,0]直接得解,可以循环这个环来构造回文,否则[1,0],[0,1],注意到当所需回文为odd长时,......
  • abc249_f Ignore Operations 题解
    IgnoreOperations题意Takahashi有一个整数\(x\),初始\(x=0\)。有\(n\)次操作。第\(i\)次操作用两个整数\(t_i,y_i\)描述:如果\(t_i=1\),将整数\(x\)替换为\(y_i\)。如果\(t_i=2\),将整数\(x\)替换为\(x+y_i\)。Takahashi可以跳过其中至多\(K\)......