Mathematically Hard LightOJ

题目链接

题意：给定一个区间[m, n]，假设 小于m的与m互质的数的个数为 s(m)，小于m+1的与m+1互质的数的个数为 s(m+1)，……，小于n的与n互质的数的个数为 s(n)。如果 m == n，输出 a = s(m)*s(m)，否则，输出 a = s(m)*s(m) + s(m+1)*s(m+1) + …… + s(n)*s(n)。数据规模为maxv = 5 * 10^6

思路：很容易想到欧拉函数打表，虽然是水题但我也要记录一下，因为我疯狂wa和re，wa的原因是需要用到ull。而re的原因居然是定义的数组太多了，太不可思议了，所以我要记录一下，因为需要定义的数组不能过多，所以需要用到Eratosthenes筛法，其时间复杂度是O(NlogN)。所以线性筛法都不行QAQ。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<algorithm>
#define N 200060
#define ll long long
#define ull unsigned long long 
using namespace std;
const int maxn=5000005;
ull ans[maxn];
void count(int n)        //求1~maxv的所有欧拉函数
{
    memset(ans,0,sizeof(ans));
    for(int i=2;i<n;i++){
        if(!ans[i])    //第一个ans[i] == 0 的都是素数
        {
            for(int j=i;j<n;j+=i)    //素数的倍数
            {
                if(!ans[j])    
                    ans[j]=j;    //对素数倍数赋值
                ans[j]=ans[j]/i*(i-1);    //求欧拉函数的值
            }
        }
    }
    for(int i=2;i<n;i++)    //求平方和
        ans[i]=ans[i-1]+ans[i]*ans[i];
}
int main()
{
    int t,u=0;
    count(maxn);
    scanf("%d",&t);
    while(t--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("Case %d: ",++u);
        printf("%llu
",ans[b]-ans[a-1]);
    }
}