fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define fi first
  5. #define se second
  6. const int N=1e5+3;
  7. int n;
  8. ll a[N];
  9. ll pf[N];
  10. ll s,t;
  11. bool vis[N];
  12. bool check(ll x){
  13. 	if(s%x!=0) return false;
  14. 	for(int i=1; i<=n ;i++) vis[i]=false;
  15. 	for(int i=1; i<=n ;i++){
  16. 		if(a[i]%x==0 || a[i]%x>n || vis[a[i]%x]) return false;
  17. 		vis[a[i]%x]=true;
  18. 	}
  19. 	return true;
  20. }
  21. ll f(ll x){
  22. 	while(x<=n) x*=2;
  23. 	return x;
  24. }
  25. void solve(){
  26.  
  27. 	// custom n = 100000
  28. 	n=100000;
  29.  
  30. 	//Let sum(a[i]-i) = s 
  31. 	s=963761198400;
  32.  
  33. 	//predefine a just to fill in array
  34. 	for(int i=0;i<=n;i++)
  35. 	a[i]=i+1;
  36. 	a[n-1]=a[n-2];
  37. 	if(s==0){cout << "YES\n";return;}
  38. 	t=s;
  39. 	int c=0;
  40. 	while(t%2==0) t/=2;
  41. 	for(ll i=1; i*i<=s ;i++){
  42. 		if(s%i!=0) continue;
  43. 			c++;
  44. 		ll x=f(i),y=f(s/i);
  45. 		if(check(x)){cout << "YES " << x << '\n';return;}
  46. 		if(check(y)){cout << "YES " << y << '\n';return;}
  47. 	}
  48. 	cout<<"Divisors: "<<c<<endl;
  49. 	cout << "NO\n";
  50. }
  51. int main(){
  52. 	ios::sync_with_stdio(false);cin.tie(0);
  53. 	int t;cin >> t;
  54. 	while(t--) solve();
  55. 	//solve();
  56. }
Time limit exceeded #stdin #stdout 5s 5536KB
comments (?)
stdin
copy 
1
stdout
copy 
Standard output is empty
https://ideone.com/f7TgQL
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!