寒假训练三

H题

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
bool prime[100005];//储存素数
int sum[100005],f[100005];//sum为因子个数，f为k和因子数
void gett(int n){
    for(int i=2;i <= n;++i)
       prime[i] = true;
      for(int i = 2;i <= n;++i){
           if(prime[i]){
                 for(int j = 2*i ; j <= n ;j+=i)//埃筛法求素数
                      prime[j] = false;
           }
           else{
                for(int j = i; j <= n ;j+=i){//此时prime[i]为合数，i的倍数的因子数含i，因子数加一
                       ++sum[j];
                }
              ++f[sum[i]];     //
           }
      }
}
int main(){
    int n,m,k;
    cin>>n>>m;
      gett(n);
    while(m--){
        cin>>k;
        cout<<f[k]<<endl;
    }
}

I题
先打表推出递推公式，找规律既可

//#include<iostream> #include<cstdio>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL ab[65]={0,0,1,4,15,58,229};//bc和ab一样 
LL ac[65]={0,1,1,3,3,9,9,31,31};
LL ba[65]={0,0,0,1,1,6,6,27,27,112,112};//cb和ba一样  
LL ca[65] = {0,0,2,12,54,224};
LL get(LL x,LL y){
    LL ans = 1;
    while(y){
        if(y&1) ans*=x;
        x *= x;
        y>>=1;
    }
    return ans;
}
int main(){
    LL n;
    cin>>n;
    for(int i = 3;i <= n/2+2; i++)
      ab[i] = 5*ab[i-1]-4*ab[i-2]-1;
    for(int i = 5;i <= n+2; i+=2 )  
      ac[i+1] = ac[i] = 2*ac[i-2]-ac[i-4]+get(4,(i-4)/2+1);
     for(int i=5;i <= n+2;i+=2) 
      ba[i+1] = ba[i] = 2*ba[i-2]-ba[i-4]+get(4,(i-4)/2+1);
      for(int i = 3; i <= n/2+2;++i)
        ca[i] = 2*ca[i-1]-ca[i-2]+ 2*get(4,i-2);


      cout<<"A->B:"<<ab[n/2+1]<<endl;
      cout<<"A->C:"<<ac[n]<<endl;
      cout<<"B->A:"<<ba[n]<<endl;
      cout<<"B->C:"<<ab[n/2+1]<<endl;
      cout<<"C->A:"<<ca[n/2]<<endl;
      cout<<"C->B:"<<ba[n]<<endl;
      cout<<"SUM:"<< (1LL<<n)-1 <<endl;
} 

以下是大佬代码

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef unsigned long long ll;
ll m=0,n=0,p=0,c=1;
ll x;
int main()
{
    cin>>x;
    for(ll i=2;i<=x;i++)
    {
        if(i%2==0)
        {
            p=n+c;
            m=n+n;
        }
        else {
            n=m+p;
            c=p+p+1;
        }
    }
    cout<<"A->B:"<<p<<'\n';
    cout<<"A->C:"<<c<<'\n';
    cout<<"B->A:"<<n<<'\n';
    cout<<"B->C:"<<p<<'\n';
    cout<<"C->A:"<<m<<'\n';
    cout<<"C->B:"<<n<<'\n';
    cout<<"SUM:"<<m+c+n+n+p+p<<endl;
}