JZOJ 5395. 【NOIP2017提高A组模拟10.6】Count

Description

Input

一行三个正整数 ，表示 ��,��,��，含义如题所示。

Output

一行一个整数表示答案������ ������������������。

Sample Input

2 3 1

Sample Output

5

Data Constraint

Hint

≤��的正整数中与��互质的数有��，平均数×��=��
≤��的正整数中与��互质的数有��、��，平均数×��=��

Solution

• 考虑当 x≥2 时 φ(x) 为一个偶数，因为对于一个 ≤x 的正整数 y，

• 如果gcd(x,y)=1 则有 gcd(x,x−y)=1 。此时不难发现 f(x)=x 。

• 因此题目变成求：

  ∑i=LRik

• 即自然数幂和！注意 f(1)=2 。不妨考虑：

  ∑i=1Rik

• 于是我们可以使用拉格朗日插值法（这里不作证明，只讲做法）。

• 对于 R 较小的情况，我们考虑快速幂直接计算。

• 对于 R 较大的情况，我们知道答案 ans(R) 是一个 k+1 次多项式。

• 根据拉格朗日插值法有：

  ans(x)=∑i=1k+2ans(i)∗∏k+2j=1,j≠i(x−j)∏k+2j=1,j≠i(i−j)

• 枚举 i，不难发现分子和分母都是连续两段数字的乘积。

• 随着 i 的增大，发现两段数字只有端点的数字发生了变化。

• 时间复杂度 O(k log k) 。

Code

#include<cstdio>
using namespace std;
typedef long long LL;
const int N=1e6+1,mo=998244353;
int l,r,k;
LL sum;
LL ans[N];
inline LL ksm(LL x,int y)
{
    LL s=1;
    x%=mo;
    while(y)
    {
        if(y&1) s=s*x%mo;
        x=x*x%mo;
        y>>=1;
    }
    return s;
}
inline LL work(int x)
{
    if(x<=k+2) return ans[x];
    LL num=0,a=1,b=1;
    for(int i=2;i<=k+2;i++)
    {
        a=((x-i+mo)%mo*a)%mo;
        b=((1-i+mo)%mo*b)%mo;
    }
    for(int i=1;i<=k+2;i++)
    {
        num=(num+ans[i]*a%mo*ksm(b,mo-2)%mo)%mo;
        a=(a*(x-i+mo)%mo*ksm(x-i-1+mo,mo-2))%mo;
        b=(b*i%mo*ksm(i-k-2+mo,mo-2))%mo;
    }
    return num;
}
int main()
{
    scanf("%d%d%d",&l,&r,&k);
    for(int i=1;i<=k+2;i++) ans[i]=(ans[i-1]+ksm(i,k))%mo;
    sum=(work(r)+mo-work(l-1))%mo;
    if(l==1) sum=(sum+ksm(2,k)-1)%mo;
    printf("%lld",sum);
    return 0;
}