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; }