codeforces706(div.2)题解

B:
Baby Badawy's first words were "AND 0 SUM BIG", so he decided to solve the following problem. Given two integers n and k, count the number of arrays of length n such that:

all its elements are integers between 0 and 2k−1 (inclusive);
the bitwise AND of all its elements is 0;
the sum of its elements is as large as possible.
Since the answer can be very large, print its remainder when divided by 109+7.

Input
The first line contains an integer t (1≤t≤10) — the number of test cases you need to solve.

Each test case consists of a line containing two integers n and k (1≤n≤105, 1≤k≤20).

Output
For each test case, print the number of arrays satisfying the conditions. Since the answer can be very large, print its remainder when divided by 109+7.
解析:
首先数组和最大,那么先将数组每一位都变为2^k-1;
其次数组所有元素与运算为0,只要从第0位到第k-1位(二进制)中每一位都有一个0存在即可.
比赛时傻了,认为只要最后一位有一个0,位运算就是0.一直卡题.
然后方法数就是n^k,注意以后快速幂函数的形参的base和power也定义为long long

#include <iostream>
#include<stdio.h>
#include <cstring>
#include <algorithm>
#include <string.h>
#include <queue>
//#include <bits/stdc++.h>
#define pb push_back
#define qc std::ios::sync_with_stdio(0);
#define maxn 0x3f3f3f
#define mod 1000000007
#define debug(x) cout<<"debug"<<x<<endl;
using namespace std;
typedef long long ll;
const int N=1e5+5;
int c[26][26];
ll fast(int x,int p)
{
    ll now=1;
    while(p)
    {
        if(p&1) now=now*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return now;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>x>>y;
        ll ans=fast(x,y);
        cout<<ans<<endl;
    }
}

C:
给一个从1到n的序列,求一个最长的子序列,使得该子序列的乘积%n==1.
思路:m%n取模的结果就是从m中尽可能的减去n的倍数,如果要求取余后的结果为1,首先m和n应该互质,理由:
m%n=(a-kb)gcd(n,m)
所以如果gcd(n,m)不为1,那么m%n一定不为1.
找到了所有与n互质的数,相乘取余后得到结果为k,由余数定义的k一定小于n,所以只要把k/k就行.

#include <iostream>
#include<stdio.h>
#include <cstring>
#include <algorithm>
#include <string.h>
#include <queue>
//#include <bits/stdc++.h>
#define pb push_back
#define qc std::ios::sync_with_stdio(0);
#define maxn 0x3f3f3f
#define debug(x) cout<<"debug"<<x<<endl;
using namespace std;
const int max_n=35;
const int min_n=10000000;
typedef long long ll;
const int N=1e5+5;
int a[N];
int vis[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=i;
    ll ans=1,sum=0;
    for(int i=1;i<=n;i++)
    {
        if(__gcd(n,i)==1)
        {
            vis[i]=1;
            ans*=i;
            ans%=n;
            sum++;
        }
    }
    if(ans!=1) vis[ans]=0,sum--;
    cout<<sum<<endl;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==1)
        cout<<a[i]<<" ";
    }


    cout<<endl;
}

扩展GCD求逆元