icontofig | 发布于 2019-09-11 08:23:30 | 阅读量 433 | 思维题 筛法
发布于 2019-09-11 08:23:30 | 思维题 筛法

题目大意

给出100个数,求问是否存在某个连续的100个φ值,使得两者一一相等。

1≤ai≤1.5*108

题解

首先其实能想到的是KMP,但是无奈这个ai太大了,用欧拉筛没办法筛出来,而且时间也不够,因为还有多组数据。

但是能够预处理一些φ还是好的,这样能降低所有数据都需要暴力算φ带来的复杂度。

然后我们猜想,是不是这100个数里面一定会有一个数对应的φ恢复到φ-1的时候是素数,也即两个相邻素数一定相隔100以内?
答案是否定的,这个可以通过打表来检查出来。

但是我们可以找到另一个问题,这100个数的φ-1中,要么就是有至少一个素数,要么就是有一个数为一个≤13的素数和一个大素数的乘积。

这样我们可以直接分开讨论,把所有可能的情况计入一个vector里面,最多出现1000种可能(实际上到不了),然后直接对于每一种可能暴力检索100个数是否符合要求即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
int phi[maxn];
int pr[maxn],np[maxn];
int cnt = 0;
void euler(){
    phi[1] = 1;
    for(int i = 2;i < maxn;++i){
        if(!np[i]){
            pr[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= cnt && i * pr[j] < maxn;++j){
            np[i*pr[j]] = 1;
            if(i % pr[j] == 0){
                phi[i*pr[j]] = phi[i] * pr[j];
                break;
            }
            else phi[i*pr[j]] = phi[i] * (pr[j] - 1);
        }
    }
    return;
}
int mx = 0,mi = 1e9;
int a[105];
int n;
int t;
int calc(int x){//暴力求解φ(x)
    int ret = x;
    for(int i = 1;i <= cnt && pr[i] * pr[i] <= x;++i){
        if(x % pr[i] == 0){
            ret /= pr[i];
            ret *= (pr[i] - 1);
        }
        while(x % pr[i] == 0)x /= pr[i];
    }
    if(x != 1){
        ret /= x;
        ret *= (x-1);
    }
    return ret;
}
vector<pair<int,int> >v;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    euler();
    cin >> t;
    while(t--){
        mx = 0;
        mi = 0;
        v.clear();
//        v.push_back(make_pair(1,1));
        for(int i = 1;i <= 100;++i){
            cin >> a[i];
            if(calc(a[i]+1) == a[i]){
                v.push_back(make_pair(i,a[i]+1));
            }
            for(int j = 1;j <= 6;++j){
                if((a[i]) % phi[pr[j]] == 0){
                    int tt = (a[i]) / phi[pr[j]];
                    if(calc(tt+1) == tt){
                        v.push_back(make_pair(i,(tt+1) * pr[j]));
                    }
                }
            }
        }
        int ans = 0;
        int cnt = 1;
        for(int i = 0;i < v.size();++i){
            int pos = 100 - v[i].first;
            pos += v[i].second + 1;
            int j;
            for(j = 1;j <= 100;++j){
                if(pos - j < maxn){
                    if(a[100-j+1] != phi[pos-j])
                        break;
                }
                else{
                    int ph = calc(pos-j);
                    if(a[100-j+1] != ph)
                        break;
                }
            }
            if(j == 101){
                ans = v[i].second - v[i].first + 1;
                break;
            }
        }
        if(ans){
            cout << "YES\n" << ans << "\n";
        }
        else cout << "NO\n";
    }
    return 0;
}



内容更新于: 2019-09-11 08:23:34
链接地址: http://blog.leanote.com/post/icontofig/3290d3a8f066

上一篇: The Preliminary Contest for ICPC Asia Xuzhou 2019 G.Colorful String PAM(回文自动机) + 可持久化线段树

下一篇: The Preliminary Contest for ICPC Asia Xuzhou 2019 I.query 树状数组 二维偏序

433 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航