【解题报告】CF DIV2 #ROUND 716A~C
比赛链接 数学场/规律场
A题5分钟速切，B题开始没看懂先看了C，发现C整不来，B整了半天打表找规律一发AC。
D貌似要分块莫队之类的还不会暂时不补
排名：4300+
A. Perfectly Imperfect Array
思路
完全平方数=完全平方数x完全平方数
所以只要看有没有非完全平方数即可。
赛后很多人FST了，原因是sqrt误差，我这里先转化成int再判断的所以没事
代码
// Problem: A. Perfectly Imperfect Array
// Contest: Codeforces - Codeforces Round #716 (Div. 2)
// URL: https://codeforces.com/contest/1514/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// FishingRod
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
#define MULINPUT
/*DATA & KEY
*/
int T;
void solve(int C)
{
//NEW DATA CLEAN
//NOTE!!!
int n;cin>>n;
bool flag=0;
for(int i=0,x;i<n;i++)
{
cin>>x;int k=sqrt(x);
if(k*k!=x)flag=1;
}
if(flag)puts("YES");
else puts("NO");
}
int main()
{
#ifdef MULINPUT
scanf("%d",&T);
for(int i=1;i<=T;i++)solve(i);
#else
solve(1);
#endif
return 0;
}
B. AND 0, Sum Big
思路
比赛的时候打表的，发现答案是
下面写一下正解思路
题意：给两个数n和k，求解满足以下条件的长度为n的数组数量，数组元素可以重复。
①数组元素大小范围：
②数组元素按位与的值为0
③数组元素的和尽可能大
要让数组元素按位与后的值为0，那么这n个数全都拆成2进制后每一位都至少包含1个0。但是要让数组元素的和尽可能大，所以不能都搞在一位。想象一下，我们有nxk的一个全为1的2维数组,现在我们对于每一列，要选出一个位置把他变为0，那么总共就是种
代码
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int,int> PII;
#define MULINPUT
/*DATA & KEY
*/
const int mod=1e9+7;
ll fp(ll a,ll b,ll mod) { ll res=1;a=a%mod; while(b) { if(b&1)res=(res*a)%mod; a=(a*a)%mod;b>>=1; }return res; }
int T;
void solve(int C)
{
//NEW DATA CLEAN
//NOTE!!!
int n,k;cin>>n>>k;
cout<<fp(n,k,mod)<<endl;
}
int main()
{
#ifdef MULINPUT
scanf("%d",&T);
for(int i=1;i<=T;i++)solve(i);
#else
solve(1);
#endif
return 0;
}
下面两题C和D参考的博客
C. Product 1 Modulo N
思路
比赛的时候找到的规律貌似是要元素内互质，然后就不确定了，也没时间实现。大佬说要用到一些数论定理
题意：给一个长度为n-1数组，其中元素一次是,我们要找到一个最长的子序列使它的乘积模上n后为1
参考这位大佬的博客 乘积可以表示为
又有
所以
然后因为互素集合子集乘积一定是与n互素，即构成kn+1的元素都与n互质
那么，我们只要从和n互素的元素中找就可以了
观察样例，和n互素的集合
5：1 2 3 4 但是没有4 1*2*3*4=24,24%5=4
8：1 3 5 7 1*3*5*7=105 105%8=1
9：1 2 4 5 7 8但是没有8 1*2*4*5*7*8=2240%9=8
那么可以分类讨论
如果prod%n==1，满足条件直接输出
如果prod%n!=1,那么去掉最后一个
为何这样做，我们设与n互素元素乘积为
因为,所以w一定和n互质。如果w为1那么直接输出，否则删除w
代码
// Problem: C. Product 1 Modulo N
// Contest: Codeforces - Codeforces Round #716 (Div. 2)
// URL: https://codeforces.com/contest/1514/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// FishingRod
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
//#define MULINPUT
/*DATA & KEY
*/
int T;
void solve(int C)
{
//NEW DATA CLEAN
//NOTE!!!
set<int>s;
int n;cin>>n;
LL prod=1;
for(int i=1;i<n;i++)
if(__gcd(n,i)==1)
{
s.insert(i);
prod=prod*i%n;
}
if(prod!=1)s.erase(prod);
cout<<s.size()<<endl;
for(auto t:s)cout<<t<<" ";
}
int main()
{
#ifdef MULINPUT
scanf("%d",&T);
for(int i=1;i<=T;i++)solve(i);
#else
solve(1);
#endif
return 0;
}
反思
A：
判断完全平方数使用sqrt的时候记得先转int防止精度问题
B:
样例规律可以考虑,没思路就暴力打表
C:
如果已知x模n为r,我们可以把式子转化为
互质：没有公共元素
与n互质元素乘积与n互质，其子集乘积也与n互质