饿了吗笔试20250314算法题第三题，简单梳理一下自己的解法

思路：首先最外层是动态规划，cnt[k]=cnt[k-1]+m;

这里cnt[k]是k计算result，tmp是(i+k)/gcd(i,k)累加，其中i属于[1,k-1];

然后说一下怎么求tmp，tmp对于k为质数和合数有不同的求法。

如果k是质数，m的结果是(k)*(k-1)*3/2;

而如果k不是质数，先假设它是质数，然后减去一个数dif。

说一下怎么求dif，对于所有比根号k小且被k整除的质数j，有k/j=c;则合数是由质数的j*(1+2+...c-1)*(c*j)/1变成了j(1+2+...c-1)*(c*j)/j，也就是(1+2+...c-1)*(c*j)，相比质数少了(j-1)(1+2+...c-1)*(c*j);所以dif就是所有比根号k小且被k整除的质数j,k/j=c,对(j-1)(1+2+...c-1)*(c*j)的累加；然后对于任意正整数n，输出cnt[n]即可；时间复杂度是nlog(n)；#笔试#

c++代码如下

#include <bits/stdc++.h>


using namespace std;
const int M = 1000000007;
const int N = 1000000;
bool ip[N+10];//判断是否是质数，true表示为合数
int cnt[N+10];//动态规划的dp数组



vector<int> edge[N+10];
void before(){
	//先把N以内的合数找到
	for(int i=2;i<N;i++){
		for(int j=i+i;j<N;j+=i){
			ip[j]=true;
		}
	}
	//p中存储N中所有素数
	vector<int> p;
	for(int i=2;i<N;i++){
		if(!ip[i]) p.push_back(i);
	}
	//初始化dp
	cnt[2]=3;
	
	for(int i=3;i<N;i++){
		long long tmp=0;
		long long dif=0;
		//如果是合数，求它相比于质数需要减的数dif
		if(ip[i]){
			for(int j=0;p[j]*p[j]<=i;j++){
				//找所有比根号i小的质数，可以推导以下的公式
				if(i%p[j]==0){
					dif+=((p[j]-1)*3/2*(i/p[j])*(i/p[j]-1))%M;
				}
			}
		}	
		tmp=(3*(i)*(i-1)/2)%M;
		
		tmp=(tmp-dif+cnt[i-1])%M;
		cnt[i]=tmp;
		
	}
	
}
void solve(){
	for(int i=2;i<100;i++){
		cout<<cnt[i]<<endl;
	}
}
int main() {
    int t=1;
//    cin>>t;
    before();
    //这里我是自己测试的代码，就没有cin输入了，如果有测试样例，可以改一下。
    while(t--){
		solve();
	}
    return 0;
}