Rain_w and Calculate

NC231693. Rain_w and Calculate

描述

Rain_w doesn't like calculate. So she wants you to help her with some questions. Firstly, Rain_w will give you an integer $k$ and an integer $q$ . Then she will ask you $q$ questions. For the i-th question, she will give you two integers $l_i$ and $r_i$ , then you should help her to calculate $\sum_{s=l_i}^{r_i}s^k$ . Because this number may be too large, she wants you to output this answer modulo 998244353. Please help her!

输入描述

The first line contains two integers  separated by a space.
Next  lines, the i-th line contains two integers  separated by a space, which describes the i-th question.

输出描述

Your output should contain  lines. For the i-th line, you should output an integer in range , which is the answer of .

示例1

输入:

2 5
1 9
2 6
8 17
95 95
9999999 10000000

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 943ms, 内存消耗: 79664K, 提交时间: 2022-01-26 13:53:52

#include<iostream> 
typedef long long ll;
using namespace std;
ll ans[10000005];
const ll mod = 998244353;
int k,q;
ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b = b >> 1) {
        if (b & 1) ans = (ll) ans * a % mod;
        a = (ll)a * a % mod;
    }
    return ans;
}
int main() 
{
    scanf("%d%d",&k,&q);
	ans[1]=1;
	for (ll i=2;i<=10000000;i++) 
	{
		if (ans[i]==0) 
		{
			ans[i]=qpow(i,k);
			for (int j=2;i*j<=10000000;j++) 
			{
				ans[i*j]=ans[i]*ans[j];
				ans[i*j]%=mod;
			}
		}
	}
	for(int i=2;i<=10000000;i++)
		ans[i]+=ans[i-1];
	for(int i=0;i<q;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		cout<<(ans[r]-ans[l-1])%mod<<endl;
	}
}