comet oj contest 8 E 神奇函数 （欧拉打表+推导）

题目描述

对 x>1x>1x>1 的整数 xxx ，定义 d(x)d(x)d(x) 是满足 y∣xy|xy∣x（y∣xy | xy∣x 表示 yyy 是 xxx 的约数）且大于 111 的最小的整数。

有一个神奇的函数 f\rm ff ，定义域为正整数且满足以下条件：

对于给定的 nnn， 求 ∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1n​f(i) 。

输入描述

本题每个测试点有多组数据，第 111 行一个整数 TTT 表示数据组数。

接下来 TTT 行，每行一个整数 nnn ， 含义见题目描述。

• 1≤T≤101\le T\le 101≤T≤10
• 1≤n≤10131\le n \le 10^{13}1≤n≤1013

输出描述

输出 TTT 行，每行一个整数，表示该组数据的答案。

样例输入 1

5
4
10
233
6666
123456

样例输出 1

5
14
513
21610
510126

提示

对于样例1的第1组数据：

f(1)=1f(1)=1\\f(1)=1

d(2)=2, f(2)=f(1)=1d(2)=2,\ f(2)=f(1)=1\\d(2)=2, f(2)=f(1)=1

d(3)=3, f(3)=f(1)=1d(3)=3,\ f(3)=f(1)=1\\d(3)=3, f(3)=f(1)=1

d(4)=2, f(4)=2×f(1)=2d(4)=2,\ f(4)=2\times f(1)=2\\d(4)=2, f(4)=2×f(1)=2

∑i=14f(i)=5\sum_{i=1}^4f(i)=5∑i=14​f(i)=5

#include <bits/stdc++.h>
using namespace std;
const long long N=5e6+50;
long long prime[N];
bool vis[N];
long long euler[N];
void prime_euler()
{
    memset(vis,0,sizeof(vis));
    memset(euler,0,sizeof(euler));
    euler[1]=1;
    vis[0]=vis[1]=1;
    long long tot=1;
    for(long long i=2; i<N; i++)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
            euler[i]=i-1;
        }
        for(long long j=1; j<tot; j++)
        {
            if(i*prime[j]>N)
                break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                euler[i*prime[j]]=euler[i]*prime[j];
                break;
            }
            else
                euler[i*prime[j]]=euler[i]*(prime[j]-1);
        }
    }
}
int main()
{
    prime_euler();
    long long t;
    long long n;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        long long tmp=sqrt(n);
        long long ans=0;
        for(long long i=1;i<=tmp;i++)
            ans+=euler[i]*(n/(i*i));
        cout<<ans<<'\n';
    }
    return 0;
}