饿了吗笔试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;
}