HPU算法协会公开课第二期： 【Wars】

A

#include<iostream>
#include<bitset>
using namespace std;
long long P,A;
const long long maxn=1e9;
bool prime(){                        //判断是否为素数
    for(int i=2;i*i<=P;i++){
        if(P%i == 0) return 1;
    }
    return 0;
}
int main(){
    while(cin>>P>>A){
        if(P==0&&A==0)break;
        long long a=A,p=P,s=1,i=0;
        while(p){          //快速幂   
            if(p & 1) s=(a*s)%P;    //取模 ((a*b)%c==((a%c)*(b%c))%c
            a=(a*a)%P;
            p>>=1;
        }
        if(s==A && prime()) cout<<"yes\n";
        else cout<<"no\n";

    }
    return 0;
}

B

#include<iostream>
using namespace std;
const int maxn=45000;
int N,T,M;
int main(){
    cin>>T;
    while(T--){
        cin>>M;
        cin>>N;
        int A,B;
        long long sum=0;
        while(N--){
            cin>>A>>B;
            long long a=A,b=B,s=1;
            while(b){        //快速幂
                if(b&1) s=(s*a)%M;
                a=(a*a)%M;
                b>>=1;
            }
            sum+=s;          //(a+b)%c==((a%c)+(b%c))%c
        }
        cout<<sum%M<<endl;
    }
    return 0;
}

C
公式:

#include<iostream>
using namespace std;
const int maxn=1000000007;

long long T,N;

long long mod(){
    long long b=N-1,a=2;
    long long s=1;
    while(b){
        if(b&1) s=(s*a)%maxn;           //快速幂
        a=(a*a)%maxn;
        b>>=1;
    }
    if(s==0)return maxn-1;          //s==0 即为1e9+7 
    else return s-1;
}
int main(){
    cin>>T;
    while(T--){
        cin>>N;
        cout<<mod()<<endl;

    }
    return 0;
}

D
把每个出现过的ID记录一下

#include<iostream>
using namespace std;
const int Max=1e4+1;
int a[Max]={0},N,ai,m,ii,M;
int main(){
    while(cin>>N){
        for(int i=0;i<Max;i++)a[i]=0;
        m=0;M=N;
        while(N--){
            cin>>ai;
            a[ai]++;
        }
        for(int i=0;i<Max;i++){
            if(m<a[i]){m=a[i];ii=i;}
        }
        if(2*m>M) cout<<ii<<endl;
        else cout<<"-1\n";
    }
    return 0;
}

E

#include<iostream>
using namespace std;
int T,N;
int main(){
    cin>>T;
    while(T--){
        cin>>N;
        long long s=1,a=N,b=N;
        while(b){
            if(b&1) s=(s*a)%10;     //快速幂，取 mod 10
            a=(a*a)%10;
            b>>=1;
        }
        cout<<s<<endl;
    }
    return 0;
}

F

#include<iostream>
using namespace std;
int N,M;
int main(){
    while(cin>>N>>M){
        if(N==0&&M==0)break;
        long long s=1,a=N,b=M;
        while(b){
            if(b&1) s=(s*a)%1000;
            a=(a*a)%1000;
            b>>=1;
        }
        cout<<s<<endl;
    }
    return 0;
}

G

#include<iostream>
using namespace std;
int T,Q;
int sum;
const int maxn=5e8;
bool iff(int mod){
    sum=0;             //零的个数
    while(mod){            
        sum+=mod/5;
        mod/=5;
    }
    if(sum>=Q)return 1;
    return 0;
}
int main(){
    cin>>T;
    for(int tail=1;tail<=T;tail++){
        cin>>Q;
        int l=0,r=maxn,mod=(l+r)/2;
        while(r>=l){            //二分法
            if(iff(mod))r=mod-1;
            else l=mod+1;;
            mod=(l+r)/2;
        }
        printf("Case %d: ",tail);
        if(sum==Q)cout<<l<<endl;  //此时l-1=r=mod
        else cout<<"impossible\n";
    }
    return 0;
}

H
acos(-1)=

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
const double pi=acos(-1);      
int T,n,b,w;
double a[10000];
double max(double a,double b){
    if(a>b)return a;
    else return b;
}
bool mes(double mod){             
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=int(a[i]/mod);
    }
    if(sum>=b)return 1;
    return 0;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>b;
        b++;double Max=0;
        for(int i=0;i<n;i++){
            cin>>w;a[i]=w*w*pi;
            Max=max(Max,a[i]);
        }
        double l=Max/b,r=Max,mod=(Max+l)/2;
        while(r-l>=0.00001){              //    二分
            //mod=(l+r)/2;
            if(mes(mod))l=mod;
            else r=mod;
            mod=(l+r)/2;
        }
        printf("%.4lf\n",mod);
    }
    return 0;
}

I

#include<iostream>
#include<cstdio>
using namespace std;
#define f(x) (8*x*x*x*x+7*x*x*x+2*x*x+3*x+6)
int T;
long long X;
bool fan(long double mod){
    if(f(mod)<X) return 1;   //判断大小关系
    else return 0;
}
int main(){
    cin>>T;
    while(T--){
        cin>>X;
        long double l=0,r=100,mod=(l+r)/2;
        while(r-l>=10e-7){                //二分法
            if(fan(mod))l=mod;
            else r=mod;
            mod=(l+r)/2;
        }
        if(X>=6 && X<=807020306)   //f(x)递增[0,100],f(0)=6,f(100)=807020306
            printf("%.4lf\n",mod);
        else cout<<"No solution!\n";
    }
    return 0;
}

J

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int T,N,S,n,sum;
int a[maxn];
int main(){
    cin>>T;
    while(T--){
        cin>>N>>S;
        sum=0;
        for(int i=0;i<N;i++){cin>>a[i];sum+=a[i];}
        if(sum<S){cout<<"0\n";continue;}    //判断是否有值
        n=a[0];
        int s,ff=1,j;
        for(int i=1;i<N;i++){a[i]+=a[i-1];if(a[i]>=S && ff){s=a[i];ff=0;j=i;}}     //前缀和，并记录第一次大于S的值
        int i=0;
        while(j<N){     //j左移，i右移，过程中保存j-i最小值
                if(j==N-1){   
                if(a[j]-a[i+1]<S)break;
                else{i++;s=min(s,j-i);}
            }
            else{
                j++;   
                while(a[j]-a[i+1]>=S){
                    i++;
                }
                s=min(s,j-i);
            }

        }
        cout<<s<<endl;

    }
    return 0;
}