题目描述 食堂第iii天有iii道菜.CYJian觉得第i天的第j道菜的美味程度为 { i j } \lbrace \frac{i}{j} \rbrace {ji}( {} 就是取小数部分),当然,CYJian是一个勇于尝试的人,所以每一道菜都会吃那么一点.现在CYJian有T个问题,每一个问题都是从第 A i A_i Ai天到第 B i B_i Bi天得到的美味值的总和.现在请你帮他算一算吧!请输出答案模 998244353 998244353 998244353的值. 输入格式 第一行一个数T。 接下来T行，每一行一共两个数，表示每一次询问的A和B。 输出格式 T行，每行一个正整数表示美味值之和.如果答案可以表示成PQ\frac{P}{Q}Q P的形式,则需要找到任意一个x使得 Q × x ≡ P ( m o d 998244353 ) Q \times x \equiv P (\bmod\ 998244353) Q×x≡P(mod 998244353),并且输出 x m o d 998244353 x \bmod 998244353 xmod998244353
输入输出样例 输入 #1 1 1 3
输出 #1 499122177
说明/提示 数据范围： 数据点范围 T= A⩽B⩽ 20 , 1 0 6 , 1 0 6 20,10^6,10^6 20,106,106
解释：设 f ( n ) = ∑ i n ∑ j = 1 i ( i j − [ i j ] ) = ∑ i n ∑ j = 1 i i ∗ j − 1 − ∑ i n ∑ j = 1 i [ i j ] f(n)=\sum_i^n\sum_{j=1}^i(\frac{i}{j}-[\frac{i}{j}])=\sum_i^n\sum_{j=1}^ii*j^{-1}-\sum_i^n\sum_{j=1}^i[\frac{i}{j}] f(n)=∑in∑j=1i(ji−[ji])=∑in∑j=1ii∗j−1−∑in∑j=1i[ji] 第一部分 ∑ i n ∑ j = 1 i i ∗ j − 1 = ∑ i n i ∗ ∑ j = 1 i j − 1 \sum_i^n\sum_{j=1}^ii*j^{-1}=\sum_i^ni*\sum_{j=1}^ij^{-1} ∑in∑j=1ii∗j−1=∑ini∗∑j=1ij−1因此我们可以预处理出来就OK 第二部分有个结论 ∑ i = 1 n d ( i ) = ∑ i = 1 n [ n i ] \sum_{i=1}^nd(i)=\sum_{i=1}^n[\frac{n}{i}] ∑i=1nd(i)=∑i=1n[in]因此我们可以预处理出来，再求和就OK
#include<iostream> #include<cstdio> #define ll long long #define N 1000003 #define mod 998244353 using namespace std; ll inv[N]={0}; ll mk[N]={0}; ll c33[N]={0}; int main(){ inv[1]=1; for(int i=2;i<N;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod; for(int i=1;i<N;i++) inv[i]=(inv[i-1]+inv[i])%mod; for(int i=1;i<N;i++) mk[i]=i*inv[i]%mod; for(int i=1;i<N;i++) mk[i]=(mk[i]+mk[i-1])%mod; for(int i=1;i<N;i++) for(int j=i;j<N;j+=i) c33[j]++; for(int i=1;i<N;i++) c33[i]=(c33[i-1]+c33[i])%mod; for(int i=1;i<N;i++) c33[i]=(c33[i-1]+c33[i])%mod; int T=0;scanf("%d",&T); while(T--){ int l=0,r=0;scanf("%d%d",&l,&r); ll ret=(mk[r]-mk[l-1]-c33[r]+c33[l-1])%mod; ret+=mod;ret%=mod; printf("%lld\n",ret); } return 0; }