CF1542C Strange Function（数论+思维）

题目传送门

非常赞的一道数论题~

题目大意

现在让f(i)为i的最小的非因子。

也就是不能整除i的最小正整数。

求∑f(i)的值。

思路

这道题首先想到从1~n去试一试，能不能整除，然后想如何去优化。

我们想到了lcm

l c m ( a 1 , a 2 , a 3 , a 4 , . . . a n ) lcm(a_1,a_2,a_3,a_4,...a_n) lcm(a1​,a2​,a3​,a4​,...an​)

一定能被 a 1 , a 2 , a 3 , a 4 , . . . a n a_1,a_2,a_3,a_4,...a_n a1​,a2​,a3​,a4​,...an​分别整除。

那么我们用数论分块的思想，从 1.... a i 1....a_i 1....ai​逐个求 l c m lcm lcm来除以n，那么就代表 1.. a i 1..a_i 1..ai​均能整除的数有几个，那么这些数的结果就一定至少往后推一位。

直到 l c m > = n lcm>=n lcm>=n为止。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector> 
using namespace std;
typedef long long ll;
const ll modd=1e9+7;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		ll ans=0,m,x=1,num=1;
		cin>>m;
		ans=m;
		while(x<=m){
			ans+=(m/x);
			ans%=modd;
			x=lcm(x,++num);
		}
		cout<<ans<<endl;
	}
}