1988: Sn 爆long long 的处理方法

题目描述

给你两个数 n, p(0 < n,p <= 10^15);

a1 = 1; 

a2 = 1+2; 

a3 = 1+2+3; 

...

an = 1+2+3+...+n 

Sn = a1+a2+a3+...+an;

求(6*Sn) % p;

输入

输入一个数 T表示有T组实例;

每组样例输入两个整数 n , p

输出

输出结果；

样例输入

2
1 1234567
2 1234567

样例输出

6
24

题目思路：数列求和公式很容易推出：3n^2+n^3+2n,但是计算过程中可能数据溢出，所以可以采用类似快速幂的处理方式，并不停取余。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<queue>
#include<math.h>
#define INF 0x3f3f3f3f
#define MAX 10000005
#define Temp 10000005

using namespace std;

long long Mul(long long a,long long b,long long p)
{
    if(b==)
        return ;
    long long ans=*(Mul(a,b/,p)%p);
    if(b%)
        ans=(ans+a)%p;
    return ans;
}

int main()
{
    int T;
    long long n,p;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&p);
        long long ans=*Mul(n,n,p)%p;
        ans=ans+Mul(n,Mul(n,n,p),p);
        ans%=p;
        ans=ans+*n%p;
        printf("%lld\n",ans%p);
    }
    return ;
}