Problem Description
Your task is simple.
You need to find the value of
.
As the value could be too large, output it modulo M.
Input
The first contains an integer T, denoting the number of the test cases.
Then there are T lines, each describing a single test case and contains two space separated integers N and M respectively.
Output
For each test case, output the value of summation modulo M on a separate line.
Constraints
1 ≤ M ≤ 100000
There are two types of datasets:
1 ≤ N ≤ 106 , 1 ≤ T ≤ 3000
106 ≤ N ≤ 1010 , 1 ≤ T ≤ 30
Example
Input:
1
4 1000
Output:
373
Explanation
14*4 + 24*2 + 34*1 + 44*1 = 373
题解
数学题折腾了一天……也是醉了。
首先向下取整的操作意味着【N/i】是成阶梯状的。那么我们可以用分块的思想,处理出每一块的和。但是不能暴力求和,这里就涉及到前缀和的思想。
给点提示:1^4+2^4+……+n^4=n(n+1)(2n+1)(3n^2+3n-1)/30,高二上数列好好学……
a mod p= [ (a*m) mod (p*m) ] / m (m为常数)
记得ans要清零,为这个倒是把自家电脑上的问题给解决了。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #define ll long long using namespace std; int T; ll n,m,ans; ll calcu(ll x,ll y)//n(n+1)(2n+1)(3n^2+3n-1)/30 { ll a,b,c,sum1,sum2,mod; mod=30*m; a=x%mod; b=(a*(a+1))%mod*(2*a+1)%mod; c=(3*a*(a+1)+mod-1)%mod; sum1=(b*c%mod)/30; a=y%mod; b=(a*(a+1))%mod*(2*a+1)%mod; c=(3*a*(a+1)+mod-1)%mod; sum2=(b*c%mod)/30; if(sum2-sum1<0) return sum2-sum1+m; return sum2-sum1; } void work() { ll i,j; ans=0; for(i=1;i<=n;i=j+1) {j=n/(n/i); ans=(ans+calcu(i-1,j)*(n/i)%m)%m; } printf("%lld\n",ans); } int main() { scanf("%d",&T); while(T--) {scanf("%lld%lld",&n,&m); work(); } return 0; }