Codeforces 716 div2

A题
题意：问能否找出一个子序列使得其积不是完全平方数
解：只要找到一个不是完全平方的元素就可以找到这样的子序列

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double eps = 1e-5;
        int t = sc.nextInt();
        while(t-- != 0) {
            int n = sc.nextInt();
            boolean f = false;
            while(n-- != 0) {
                int x = sc.nextInt();
                if(Math.abs((int)Math.sqrt(x) * (int)Math.sqrt(x) - x) < eps) continue;
                //System.out.println("asdlfjs");
                f = true;
            }
            if(f) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

B题
题意：问有多少个长度为n的数组满足：
所有元素都在0~(2^k)-1,所有元素and的值为0，元素的和尽可能大
解：n个数中，每个数字二进制下都有k位，对于每一位，和尽可能大且and值为0的操作是有一个数字的这一位是0，其余都是1。答案是n^k

import java.util.Scanner;

public class Main {

    final static long p = (long)1e9 + 7;

    public static long ksm(long a,long b) {
        long s = 1;
        while(b != 0) {
            if((b & 1) != 0) s = s * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return s % p;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- != 0) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            System.out.println(ksm(x,y));
        }
    }
}

C题
题意：给出n，从[1,2,3...n-1]中找出最长的子序列，使其乘机x%n = 1
解：首先，假定我们选择的序列包含数a,设其他数的乘积为x(mod n)，那么就有a∗x≡1(modn)，也就是x是a的逆元。那么a就要满足gcd(a,n)=1，否则a没有逆元，不可能入选
把所有与n互质的数在模n意义下乘起来，可以得到一个小于n的数ans，ans一定与n互质。那么ans一定在前面出现过，如果ans≠1，那么在答案序列中把那个数删掉就行了。
假设出了ans以外，其他数的乘积为y，那么就有ans ∗ y mod n = ans,得到y mod n=1。

import java.util.Scanner;

public class Main {

    public static int gcd(int a,int b) {
        if(b == 0) return a;
        return gcd(b,a % b);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = 1;
        int[] a = new int[100010];
        int n = sc.nextInt();
        long ans = 1;
        for(int i = 1;i <= n; ++i)
            if(gcd(i,n) == 1) {
                a[t++] = i;
                ans = ans * i % n;
            }
        if(ans != 1) {
            boolean f = false;
            System.out.println(t - 2);
            for(int i = 1;i < t; ++i) {
                if(a[i] == ans) continue;
                if(f == true) System.out.print(" ");
                f = true;
                System.out.print(a[i]);
            }
            System.out.println();
        }
        else {
            System.out.println(t - 1);
            for(int i = 1;i < t; ++i)
                System.out.print(a[i] + ((i == t - 1)?"\n":" "));
        }
    }
}

D题
题意：长度为n的数组和q个询问，每次询问区间[l,r]里的数最少要分成几组才能使每组内出现次数最多的都不超过(n/2向上取整)
解：
可以用vector记录每个数出现的位置，然后二分找出在某个区间内出现的次数。
怎样知道在这个区间内哪个数的出现次数最多呢？
线段树维护
假设区间有x个数，出现次数最多的数字出现了f次
f <= (x/2向上取整) 1
f > (x/2向上取整) 剩下的x-f最多可以与x-f+1个数合成一组，剩下的每个数都自己一组,那么就是f-(x-f+1) + 1 = 2*f-x

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 10;
#define lt(x) x << 1
#define rt(x) x << 1 | 1
int n,q,s,e;
vector<int>v[maxn];
int a[maxn],t[maxn * 4];

int getnum(int l,int r,int x)
{
    return upper_bound(v[x].begin(),v[x].end(),r) - lower_bound(v[x].begin(),v[x].end(),l);
}

int mymax(int x,int y,int l,int r)
{
    int t1 = getnum(l,r,x),t2 = getnum(l,r,y);
    if(t1 > t2) return x;
    return y;
}

void build(int x,int l,int r)
{
    if(l == r)
    {
        t[x] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lt(x),l,mid);
    build(rt(x),mid + 1,r);
    t[x] = mymax(t[lt(x)],t[rt(x)],l,r);
}

int query(int x,int l,int r)
{
    if(s <= l && r <= e) return getnum(s,e,t[x]);
    int mid = (l + r) >> 1;
    int t1 = 0,t2 = 0;
    if(s <= mid) t1 = query(lt(x),l,mid);
    if(e > mid) t2 = query(rt(x),mid + 1,r);
   // cout<<t1<<' '<<t2<<endl;
    return max(t1,t2);
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i = 1;i <= n; ++i)
    {
        cin>>a[i];
        v[a[i]].push_back(i);
    }
    build(1,1,n);
    while(q--)
    {
        cin>>s>>e;
        cout<<max(1,2 * query(1,1,n) - (e - s + 1))<<'\n';
    }
    return 0;
}