開學之後就沒咋打過CF了，天天早八打CF屬實有點扛不住，準備藍橋杯也有一陣沒做CF的題了，碰到一場九點半的div2，就試了一把。。。
A. Perfectly Imperfect Array
題目大意：給定一個長度為n 的數組a，問是否存在一個非空子序列其中的所有元素的乘積不是一個平方式。
思路：我們隻需找到數組中是否存在一個數不是平方數，如果存在這個數，則該數組不成立，若不存在則答案成立。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include<algorithm>
#include <queue>
#include<string>
#include<map>
#define mod 1000000009
using namespace std;
int cnt;
const int N = 100010;
typedef long long ll;
typedef pair<int, int> pii;
int a[N];
map<int, int>mp;
int main() {
int t;
cin >> t;
for (int i = 1; i <= 100; i++) {
mp[i*i]++;
}
while (t--)
{
int n;
cin >> n;
int flag = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (mp[a[i]] == 0)flag = 1;
}
if (!flag) {
puts("NO");
}
else puts("YES");
}
}
B. AND 0, Sum Big
題目大意：
給出n , k 要求輸出滿足以下條件的數組的數量，答案模1 e 9 + 7 。
（1）數組的元素大小在[ 0 , 2^k-1 ]中
（2）所有元素按位與之後的結果是0。
（3）數組元素的和盡量大。
思路：
賽時看到題人是懵的，賽後仔細思考才明白了題意。其實就是給出n個數，每個數的二進制表達占一行，每個數的二進制表達都是k位，于是我們就組成了一個nk的矩陣，要想使得所有元素按位與之後的結果為0的話，每一列的二進制表達上都必須至少存在一個0，而如果與此同時我們要滿足條件3，是元素之和盡量大，是以我們每一列中，隻讓一個元素為0，即最後變成了一個排列組合問題：在一個nk的矩陣中，另每一列的任一位為0的方案數有多少，答案也就是你n^k.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include<algorithm>
#include <queue>
#include<string>
#include<cmath>
#include<map>
#define mod 1000000007
using namespace std;
int cnt;
const int N = 100010;
typedef long long ll;
typedef pair<int, int> pii;
ll a[N];
map<int, int>mp;
int main() {
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
long long ans = 1;
for (int i = 1; i <= k; i++) {
ans *= n;
ans = ans % mod;
}
cout << ans << endl;
}
}
C. Product 1 Modulo N
題目大意：
給出一個數n，從1-n-1挑出幾個數組成一個最長序列，該序列的所有元素的乘積mod n = 1。
（賽時了解題意想了半天。。）
思路：
由于要求序列最長，是以所有的答案中都要将1包含進去，随後我們就要尋找我們的答案，首先我們要排除所有與 n 不互質的數，因為如果一個數與 n 不互質那麼他的gcd(n, n % x) != 1即此時，任何情況下都不能滿足乘積mod n = 1，是以我們将互質的數放入依次數組中，并且計算其乘積 mod n = 1，如果最後發現餘數不為 1 ，彈出最後一個數即可（這裡聽說是威爾遜定理的一個推廣，本人對數論研究不深，就不做贅述了）。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include<algorithm>
#include <queue>
#include<string>
#include<cmath>
#include<map>
#define mod 1000000007
using namespace std;
const int N = 100010;
typedef long long ll;
typedef pair<int, int> pii;
ll a[N];
map<int, int>mp;
int n;
int ans[N];
bool st[N];
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
ll flag = 1;
cin >> n;
int k = 0;
for (int i = 1; i < n; i++) {
if (gcd(i, n) == 1) {
ans[k++] = i;
flag *= i;
flag %= n;
}
}
if (flag == 1) {
cout << k << endl;
for (int i = 0; i < k; i++)
cout << ans[i] << ' ';
}
else {
cout << k - 1 << endl;
for (int i = 0; i < k - 1; i++)
{
cout << ans[i] << ' ';
}
}
cout << endl;
}