icontofig | 发布于 2019-09-11 08:23:30 | 阅读量 381 | 思维题 筛法
发布于 2019-09-11 08:23:30 | 思维题 筛法
The 2019 Asia Nanchang First Round Online Programming Contest A.Enju With math problem 思维题 欧拉筛
题目大意给出100个数,求问是否存在某个连续的100个φ值,使得两者一一相等。 1≤ai≤1.5*108 题解首先其实能想到的是KMP,但是无奈这个ai太大了,用欧拉筛没办法筛出来,而且时间也不够,因为还有多组数据。 但是能够预处理一些φ还是好的,这样能降低所有数据都需要暴力算φ带来的复杂度。 然后我们猜想,是不是这100个数里面一定会有一个数对应的φ恢复到φ-1的时候是素数,也即两个相邻素数一定相隔100以内?答案是否定的,这个可以通过打表来检查出来。 但是我们可以找到另一个问题,这100个数的φ-1中,要么就是有至少一个素数,要么就是有一个数为一个≤13的素数和一个大素数的乘积。 这样我们
继续阅读