20241207下午训练

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

Code:

CPP

#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:

CPP

#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:

CPP

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

文章操作

相关推荐

评论

20241207下午训练