Codeforces Round ＃716 (Div. 2)

2021.4.19

A

The question ： Here you are. n Sequence of Numbers , Ask you if there is a subsequence whose product is not a square number

Answer key ： Judge n Whether the sequence of numbers is a complete square number

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int n,x,t;
    cin>>t;
    while(t--){
    cin>>n;
    int flag=0;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        int k=(int)sqrt(x);
        if(k*k!=x)
            flag=1;
    }
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    }
    return 0;
}

B

The question ： Enter two numbers n and k, It is required to construct a n Sequence of Numbers , And selected n Number needs to be from 0~ To choose , All elements are required to be bitwise AND 0 And the sum of all elements is the largest , Find the number of schemes that can be constructed .

Answer key ： Sequence from 0~ Choose from , So it can be seen that every number can be reduced to a length of k Binary number of , All elements are required to be bitwise AND 0,k Bit binary each bit must have one 0, this k individual 0 It's from n Number of contributions , Demand and maximum , So every one has and only one 0, All the others in the same position should be 1, So each of these 0 Can be placed in n On the corresponding bit of the number , every last 0 Yes n A choice , All in all k individual 0, The answer is %1e9+7.

#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
#define mod 1000000007
using namespace std;
ll qpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b%2)
            res=res*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return res;
}
int main()
{
    ll t,n,k;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        cout<<qpow(n,k)%mod<<endl;
    }
    return 0;
}

C

The question ： Enter a number n, from  [1,2,…,n−1] Select the sequence with the longest length , Make the product of the sequence remainder n by 1

Answer key ：

Pei genus theorem ： For non negative integers a,b, There is x,y bring ax+by=gcd(a,b), in other words ax+by The smallest positive integer that can be formed is gcd(a,b), Be careful (a,b Different at the same time 0)

ax+by=c There is a solution if and only if c%gcd(a,b)==0, If gcd(a,b)>1 that c Must be greater than 1, therefore gcd(k,n)>1,, So the product of the sequence is required %n=1, Need from gcd(k,n)=1 Middle search .

Make ：, At this time sum[1,n), The remainder is required to be 1, be ans=sum/sum=1, Let's put the in the product sum Removing the product of the sequence is 1, In this way, we only need to delete one number to get the product remainder of the sequence n by 1.

What then? sum It must be in s Li ？

Suppose there is no mold , And that's what we end up with ans%n=1, therefore ans It must be s The product of the numbers in , and sum yes s The product of all numbers in ,ans*x=sum, So this x It must be s Number in Li , That is, after the above mold taking sum, So you can go from s Removed from .

#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    ll n,ans=1,a[100005],l=0;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        if(gcd(i,n)==1){
            a[l++]=i;
            ans=(ans*i)%n;
        }
    }
    if(ans!=1){
    cout<<l-1<<endl;
    for(int i=0;i<l;i++)
        if(a[i]!=ans)
            cout<<a[i]<<' ';
    }
    else{
    cout<<l<<endl;
    for(int i=0;i<l;i++)
        cout<<a[i]<<' ';
    }
    cout<<endl;
    return 0;
}