【玲珑】1144 - 数论你还会快速幂（思维 & 快速幂 & 快速乘）

FishWang

发布于 2025-08-27 12:21:17

12200

代码可运行

运行总次数：0

代码可运行

题目链接：点击打开题目

这个题是根据别人发现的规律才写出来的。分析链接：点击打开链接

知道了规律后，我们把题目的表达式变化一下：

\sum_{i=1}^{n}i^k\%p=\sum_{i=1}^{p-1}i^k\%p+\sum_{i=p}^{n}i^k\%p

根据规律：如果k为(MOD-1)的倍数时，每(MOD-1)个数算出的值为(MOD-1)，否则，值为0。

我们可以得到前面算式的值，因为0≤n−p≤100，所以后面的值可以用循环去暴力求解。

然后就是注意一下暴力求解的时候，快速幂的地方会爆longlong，所以再用快速乘就好。

代码如下：

#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
LL MOD;
LL QuickMultiply(LL a,LL b)
{
    LL ans = 0;
    while (b)
    {
        if (b & ((LL)1))
            ans = (ans + a) % MOD;
        a = (a + a) % MOD;
        b >>= 1;
    }
    return ans;
}
LL QuickMod(LL a,LL pow)
{
    LL ans = 1;
    while (pow)
    {
        if (pow & ((LL)1))
            ans = QuickMultiply(ans,a) % MOD;
        a = QuickMultiply(a,a) % MOD;
        pow >>= 1;
    }
    return ans;
}
int main()
{
    LL n,k,ans;
    int T;
    scanf ("%d",&T);
    while (T--)
    {
        scanf ("%lld %lld %lld",&n,&k,&MOD);
        if (k == 0)
        {
            cout << n%MOD << endl;
            continue;
        }
        //如果k为(MOD-1)的倍数时，每(MOD-1)个数算出的值为(MOD-1)，否则，值为0
        if (k % (MOD-1) == 0)
            ans = MOD-1;
        else
            ans = 0;
        for (LL i = MOD ; i <= n ; i++)
        {
            ans = (ans + QuickMod(i,k)) % MOD;
        }
        cout << ans << endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-07-19，如有侵权请联系 cloudcommunity@tencent.com 删除

include