Does it not suffice to check for all factors of (n+1) if they produce the permutation or not?
The question is basically trying to ask, find an integer x such that, all the elements of the given array can be written as (m1x + 1), (m2x + 2), … , (mn*x + n) where m1, m2, m3, …, mn are some integers.
Here, I have assumed mx + (n+1) == 0 for some integer m. (Maybe I went wrong here).
This gives me mx = -(n+1) => m = -(n+1)/x . Since m is a integer, x | (n+1).
So I have checked for all factors x of n+1, if the condition in the question satisfies. It passes the sample test case but gives WA on all other ones ;(.
Help!
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define int ll
#define SETUP ios_base::sync_with_stdio(0);cin.tie(0);init();
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define ed '\n'
#define bug(x) cout << #x << " = " << x << "\n";
#define bugv(x) for(auto i:x){cout << i << ' ';} cout << ed;
#define TEST int t;cin >> t;while(t--)tc();
#define TEST0 tc();
#define GTEST int tt;cin >> tt;for(int t=1;t<=tt;t++){cout << "Case #" << t << ": ";tc();}
#define SORT(v) sort(all(v));
#define REV(v) reverse(all(v));
#define bs(a,x) binary_search(all(a),x);
#define vi vector<int>
#define mpii map<int,int>
#define here cout << "here\n"
#define prii pair<int,int>
#define ONLINE_JUDGE
//#define pbds
#ifdef pbds
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <numeric>
using namespace __gnu_pbds;
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#endif
using namespace std;
void init(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
template <typename t>
t gcd(t x, t y){
if(y==0)return x;
return gcd(y,x%y);}
template <typename t>
t vgcd(vector<t>a){t res = a[0];ll n= a.size();for(ll i=1;i<n;i++){res = gcd(a[i],res);if(res==1)return 1;}return res;}
bool cmp_str_len(string s1,string s2){return s1.size()<s2.size();}
bool cmp_pair_f(pair<int,int>x,pair<int,int>y){return x.ff<y.ff;}
bool cmp_pair_s(pair<int,int>x,pair<int,int>y){return x.ff>y.ff;}
template <typename t>
t ncr(t n , t r){
if(r==0){
return 1;
}
ll N = 1;
ll R = 1;
while(r){
N*=n;
R*=r;
ll g = gcd(N,R);
N/=g;
R/=g;
n--,r--;
}
return N;}
template <typename t>
t powermod(t x, t y, t m){
int r = 1;
x=x%m;
if(!x)return 0;
while(y>0){
if(y&1){
r = (r*x)%m;
}
y = y>>1;
x = (x*x)%m;}return r;}
const int mod = 1e9+7;
//===================================================================================================================================================
int mex(vector<int> a){
sort(all(a));
int r = 1;
int n = a.size();
for(int i=0;i<n;i++){
if(a[i]==r) ++r;
}
return r;
}
vector<int> appmod(vector<int> a, int m){
for(auto &x:a){
x = x%m;
}
return a;
}
vi factors(int n){
vi ret;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
if(n/i == i){
ret.pb(i);
}else{
ret.pb(n/i);
ret.pb(n/i);
}
}
}
ret.pb(n);
return ret;
}
void tc(){
int n;
cin >> n;
vi a(n);
for(int i=0;i<n;i++){
cin >> a[i];
}
vi fac = factors(n+1);
vi b;
//bugv(fac)
for(auto x:fac){
b = a;
//bug(mex(appmod(b,x)))
if(mex(appmod(b,x))==n+1){
cout << "YES " << x << ed;
return;
}
}
cout << "NO\n";
}
signed main(){
SETUP
TEST
//GTEST
}