Codeforces Round #729 (Div. 2)C. Strange Function

C. Strange Function:
题意:
t组输入,每一次一个n,求f(1)+f(2)+…+f(n)对1e9+7取模;
f(i)表示最小的不能被i整除的数。
例如:f(1) = 2;f(2)=3;f(3)=2;f(10)=3,f(12)=5;

分析:
由f(i)的定义可知f(i)最小为2。
我们可以首先假定所有f(i)=2(i=1~n)。然后我们思考,什么时候f(i)会为3?当然是1和2都是i的因子;同理,当1,2,3都是i的因子时f(i)为4,一般地,当1,2,3…(k-1)都是i的因子时f(i)为k。
所以我们只需依此求出因子分别为{1}、{1,2}、{1,2,3}…{1,2,3…x}的数的个数,而求因子为{1,2,…k}的数的个数为n/lcm(1,2,…k)。
当我们求所有f(i)=3的对答案的贡献时,由于我们初始f(i)=2,我们只需在每个f(i)的基础上加1,而加1就是加f(i)=3的数目。

而我们每次都是在lcm(1,2…k-1)的基础上求lcm(1,2,…k),当然因子为lcm(1,2,…k)的集合是被因子为lcm(1,2…k-1)的集合包含的,所以计算结果时依然只加1。

代码:

#include<bits/stdc++.h>
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int INF = 2147483647;
const int mod =1e9+7;
const int Max = 3e5+20;
ll gcd(ll a,ll b)
{
    if(a<b) swap(a,b);
    return a%b==0?b:gcd(a%b,b);
}
ll lcm(ll a,ll b)
{
    return a*b/gcd(a,b);
}
int main()
{

     int t;
     ll n;
     cin>>t;
     while(t--)
     {
         cin>>n;
         ll ans = 2*n%mod;//初始每个f[i]=2,答案即为2*n
         ll g = 1;
         for(int i=2;;++i)
         {
             g=lcm(g,i); //求1~i的最小公倍数
             ans=(ans+n/g)%mod;
             if(g>n) break;

         }
         cout<<ans<<endl;
     }

     return 0;
}


上一篇:求多个数的最大公约数,最小公倍数


下一篇:最大公约数和最小公倍数(辗转相除法)