CF 1542C C. Strange Function

本文主要是介绍CF 1542C C. Strange Function，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://codeforces.com/problemset/problem/1542/C

题意：
定义\(f(i)\)表示最小的不能整除i的数，求\(\sum_{i=1}^nf(i)\)

若\(f(i)=x\)，说明\(1|i,2|i,3|i,……(x-1)|i，x \nmid i\)，即\(lcm(1,2,3,……,x-1) | i,x \nmid i\)
所以\(f(i)>=x\)的\(i\)的个数等于 \(n/lcm(1,2,3,……,x-1)\)
\(f(i)=x\)的\(i\)的个数等于 \(n/lcm(1,2,3,……,x-1)\) - \(n/lcm(1,2,3,……,x-1,x)\)

#include<bits/stdc++.h>

using namespace std;

long long getgcd(long long a,long long b)
{
	return __gcd(a,b);
}

long long getlcm(long long a,long long b)
{
	return a/getgcd(a,b)*b;
}

int main()
{
	int T;
	long long n,lcm;
	const int mod=1e9+7;
	int ans;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld",&n);
		ans=0;
		lcm=1;
		for(int i=1;;++i)
		{
			lcm=getlcm(i,lcm);
			if(lcm>n) break;
			ans+=n/lcm%mod;
			ans%=mod;
		}
		ans=(ans+n)%mod;
		printf("%d\n",ans);
	}
}

这篇关于CF 1542C C. Strange Function的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！