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