hdu6169 数论思维DP 2017多校第九场1009

118 阅读 0 评论 78 点赞

我是靠谱客的博主聪明白云，最近开发中收集的这篇文章主要介绍hdu6169 数论思维DP 2017多校第九场1009，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

给定区间[L,R]和一个整数K，问区间内所有满足其最小因子(1除外)为K的数的和。L,R,K的范围是(<=1e11) 结果mod1e9+7

题解

首先，根据唯一分解定理，我们知道一个数一定能分解成若干个素数的幂的乘积。那么我们现在考虑一个数的最小因子为k，这个数应该满足什么条件？显然，首先k必须是素数，否则不可能有数的最小因子是k。其次这个数必须由k及比k大的素数的幂的乘积组成。
我们想到上面之后就应该自然想到要分k为素数和k不为素数考虑。
这里数的范围为1e11，那么我们如何判断这个范围内的一个数是不是素数？这个思想和2017多校第四场的1003就类似了。就是对于n以内的数，[ $sqrt n$ -n]中的数没有被[1- $sqrt n$ ]中素数筛出来的数一定是素数。所以对于这题我们只需求出 $sqrt{10^{11}}$ （大约320000）范围的素数即可。

2017多校第四场的1003

如果k不为素数，没什么说的，结果一定是0。
如果k为素数，那么现在我们要求的就是[l,r]范围里面满足由k及比k大的素数的幂的乘积组成的数的总和。
这里我们又可以分情况讨论了。

如果k>=320000，因为我们求的是由k及比k大的素数的幂的乘积组成的数的总和，所以这个数一定会大于1e11，所以现在我们只需考虑k本身。如果k在[l,r]的范围里面，那么结果肯定就是k%mod，否则就是0。
如果k<320000，现在我们的问题就是快速求出[l,r]范围内由k及比k大的素数的幂的乘积组成的数的总和。我们考虑DP。（至于为什么想到DP，QAQ，比赛的时候没有想到，看了题解才会，所以我也不知道）
我们设dp[i][j]表示[1,l]范围的数被前j个素数筛去后剩下数的总和。（筛去的意思就是[l,r]范围的数中去掉由前j个素数及比之大的素数的幂的乘积组成的数）
那么状态转移方程为：dp[i][j] = dp[i][j-1]-prime[j]*dp[i/prime[j]][j-1]
（prime[j]代表第j个素数）
主要说一下prime[j]*dp[i/prime[j]][j-1]，其实就是在[1,i]中由k及比k大的素数的幂的乘积组成的数。dp[i/prime[j]][j-1]就是范围[1,i]里面k的倍数中比k大的倍率的倍数的倍率的和。多体会几遍应该就懂了。

现在剩下最后一个问题。320000范围里素数大约有30000个，l和r的范围为1e11，那么我们dp的数组肯定开不下。所以我们小范围记忆化，大范围搜索。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 320005;
const int len = 1e5+5;
const int p_m = 105;
const int mod = 1e9+7;
ll l,r,k,prime[maxn];
int num;
ll dp[len][p_m],inv2;
bool isprime[maxn];
map<ll,int> mp; //mp[i]=j代表i这个素数是第j个素数

ll pow_mod(ll a,ll b)  //快速幂，用来求逆元
{
    ll res=1;
    while(b)
    {
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}

void get_Prime()
{
    num = 0;
    memset(isprime,true,sizeof(isprime));
    for(ll i=2;i<maxn;i++)
    {
        if(isprime[i])
        {
            prime[++num] = i;
            mp[i]=num;
        }
        for(int j=1;j<=num&&prime[j]*i<maxn;j++)
        {
            isprime[i*prime[j]] = false;
            if(i%prime[j]==0) break;
        }
    }
}

void init()
{
    memset(dp,0,sizeof(dp));
    for(ll i=1;i<len;i++)
    {
        for(int j=0;j<p_m;j++)
        {
            if(j==0)
            {
                dp[i][j] = (i+1)*i/2;
                dp[i][j] %= mod;
            }
            else
            {
                dp[i][j] = dp[i][j-1]-prime[j]*dp[i/prime[j]][j-1]%mod;
                dp[i][j] = (dp[i][j]+mod)%mod;
            }
        }
    }
    inv2 = pow_mod(2,mod-2);
}

ll dfs(ll x,int a)
{
    if(x<len && a<p_m) return dp[x][a];
    if(a==0) return x%mod*(x%mod+1)%mod*inv2%mod;
    if(x<=1) return x;
    if(a && prime[a]>x) //算是一个小优化，去掉的话会TLE
    {
        while(a && prime[a]>x) a--;
        return dfs(x,a);
    }
    return (dfs(x,a-1)-prime[a]*dfs(x/prime[a],a-1)%mod+mod)%mod;
}

int main()
{
    int t;
    get_Prime();
    init();
    scanf("%d",&t);
    for(int ca=1;ca<=t;ca++)
    {
        scanf("%lld%lld%lld",&l,&r,&k);
        printf("Case #%d: ",ca);
        if(k>=maxn)
        {
            bool flag = false;
            for(int i=1;i<=num && prime[i]*prime[i]<=k;i++)
            {
                if(k%prime[i]==0)
                {
                    flag=true;
                    break;
                }
            }
            if(flag) printf("0n");
            else
            {
                if(k<=r && k>=l) printf("%lldn",k%mod);
                else printf("0n");
            }
        }
        else
        {
            ll ans;
            if(mp[k]>0)
            {
                ans = dfs(r/k,mp[k]-1)*k%mod-dfs((l-1)/k,mp[k]-1)*k%mod;
                ans = (ans+mod)%mod;
                printf("%lldn",ans);
            }
            else printf("0n");
        }
    }
    return 0;
}