20241207下午训练

sunpeilun · 2024-12-07 16:45:08 · 个人记录

T2
分解质因数+筛法。
代码中的fj函数为分解质因数的模板，由于把每个数的质因数都分解完再加起来，最终结果是不变的，所以我们可以从2到n全都调用一遍fj函数。（记得按题目要求输出）

Code:

#include<iostream>
using namespace std;
int n,arr[10001],fl=1,f[10001];
void fj(int x){
    for(int i=2;i<=x;i++){
        while(!f[i] && x%i==0){
            arr[i]++;
            x/=i;
        }
    }
}
int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        if(!f[i]){
            for(int j=2*i;j<=n;j+=i) f[j]=1;
        }
    }
    for(int i=2;i<=n;i++) fj(i);
    for(int i=2;i<=n;i++){
        if(arr[i] && fl){
            fl=0;
            cout<<i<<"^"<<arr[i]<<" ";
        }else if(arr[i]) cout<<"* "<<i<<"^"<<arr[i]<<" ";
    }
    return 0;
}

T3
数学题，推理如下：

1是n个数的因数，2是\frac{n}{2}个数的因数，3是\frac{n}{3}个数的因数……，以此类推，会发现答案为n+\frac{n}{2}+\frac{n}{3}+……+\frac{n}{n}，时间复杂度为O(n)，可以通过本题。

(话说T4提供的代码就是答案欸)
Code:

#include<iostream>
using namespace std;
int n;
long long H(int n){
    long long res=0;
    for(int i=1;i<=n;i++) res=(res+n/i);
    return res;

}
int main(){
    cin>>n;
    cout<<H(n);
    return 0;
} 

T5
暴力出奇迹（记得开long long）
Code:

#include<iostream>
using namespace std;
int n,k;
long long ans; 
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) ans=(ans+k%i);
    cout<<ans;
    return 0;
}