【Codeforces Round #716 (Div. 2) 】Codeforces-1514

A. Perfectly Imperfect Array

多個完全平方數的乘積也是完全平方數，如要找到一個非空子序列的乘積不是完全平方數的話，只要原序列中存在非完全平方數即可，

void solves(){
	int n,po;cin>>n;
	int flag=0;
	while(n--){
		cin>>po;
		int i=(int)sqrt(po);
		if(i*i!=po) flag=1;
	}
	cout<<(!flag ? "NO":"YES")<<endl;
}

B. AND 0, Sum Big

1.陣列中元素不大于 2 k ? 1 2^k-1 2k?1，即每個元素在二進制中最大為k位；
2.要滿足所有元素按位&運算為0，即陣列中每個元素化為二進制對齊后，每個位數至少有一個0，說的可能有點抽象，舉個例子：
在n=3，k=5時，在不考慮【元素和盡量大】這一條件的時候，可能滿足按位&=0的陣列有：
a[0]=0 1 1 0 1 ( 2 ) _{(2)} (2)?
a[1]=1 0 0 1 0 ( 2 ) _{(2)} (2)?
a[2]=0 1 1 0 1 ( 2 ) _{(2)} (2)?
即化為二進制對齊后，每列至少存在一個0
3.要滿足陣列元素和盡量大，則要滿足每列的1盡可能多，則只需要每列存在一個0時滿足題意，此時陣列元素和為 ( 2 k ? 1 ) ? ( n ? 1 ) (2^k-1)*(n-1) (2k?1)?(n?1)，
如例子：
在n=3，k=5時：
a[0]=1 1 1 0 1 ( 2 ) _{(2)} (2)?
a[1]=1 0 0 1 0 ( 2 ) _{(2)} (2)?
a[2]=0 1 1 1 1 ( 2 ) _{(2)} (2)?
4.分析完題意所給的條件后，我們知道，0在每一列中有n種放置情況，共有k列，即答案為 n k n^k nk，由于n的范圍到了1e5，可用快速冪水一下，

ll qpow(ll b,ll p){
	ll r=1;
	while(p){
		if(p&1) r=(r*b)%mod;
		b=(b*b)%mod;
		p/=2;
	}
	return r%mod;
}
void solves(){
	int n,k;cin>>n>>k;
	cout<<qpow(n,k)<<endl;
}

C. Product 1 Modulo N

首先我們記 a n a_n an?為數列[1,2,…n-1]，
再記所求為 A = ∏ i = 1 k a k i A=\prod_{i=1}^ka_{k_i} A=∏i=1k?aki?? 其中k為最長子序列的長度， k i k_i ki?為原序列下標，
要滿足A%n=1，則分以下兩種情況討論：
1.當A<n時，A=1，此時k=1.
2.當A>n時，由輾轉相除法易得A與n的最大公約數為1，即A與n互質，即A與n沒有相同的質因子，由于 A = ∏ i = 1 k a k i A=\prod_{i=1}^ka_{k_i} A=∏i=1k?aki??，所以n與 a k i a_{k_i} aki??互質，
此時我們再把 a n a_n an?中所有與n互質的元素累乘，記為 B = ∏ i = 1 q a q i B=\prod_{i=1}^qa_{q_i} B=∏i=1q?aqi??，其中 q i q_i qi?為與n互質的 a i a_i ai?下標，再記余數C=B%n，
由gcd(B,n)=gcd(B%n,n)，且gcd(B,n)=1，可得余數C與n互質，即C為B的因子，此時B/C=A即為所求，

void solves(){
	int n,k;cin>>n;
	vector<int>ans;
	ll sum=1;
	for(int i=1;i<n;++i){
		if(__gcd(i,n)==1){
			ans.push_back(i);
			sum=(sum*i)%n;
		}
	}
	if(sum==1){
		cout<<ans.size()<<endl;
		for(auto& it:ans) cout<<it<<" ";cout<<endl;
	} else{
		cout<<(int)ans.size()-1<<endl;
		for(auto& it:ans){
			if(it!=sum) cout<<it<<" ";
		}cout<<endl;
	}
}