The 2019 Asia Nanchang First Round Online Programming Contest A.Enju With math problem 思维题 欧拉筛

1≤ai≤1.5*108

## 题解

```#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;
}```

0 条评论