首页 > 代码库 > ZZNU 1988: Sn

ZZNU 1988: Sn

题目描述

给你两个数 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
 

输出

 输出结果;

样例输入21 12345672 1234567样例输出624

题目链接:http://acm.zznu.edu.cn/problem.php?id=1988

*********************************************

分析:公式n*(n+1)*(n+2)%p;

两个 long long 的数直接相乘会爆long long,所以两两相乘。

AC代码:

 1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include<limits.h> 6 #include <cmath> 7 #include <cstdlib> 8 #include <stack> 9 #include <vector>10 #include <queue>11 #include <map>12 13 using namespace std;14 15 #define N 200000016 #define INF 0x3f3f3f3f17 #define met(a, b) memset (a, b, sizeof (a))////  met (dist, -1);18 #define LL long long19 20 LL q(LL a,LL b,LL p)21 {22    if(b==0)23     return 0;24 25    LL ans=2*q(a,b/2,p)%p;26 27    if(b%2)28     ans=(ans+a)%p;29    return ans;30 }31 int main()32 {33     int T;34     LL n,p;35 36     scanf("%d", &T);37 38     while(T--)39     {40        scanf("%lld %lld", &n,&p);41 42        LL ans=q(n+1,n,p);43        ans=q(ans,n+2,p);44        printf("%lld\n", ans);45     }46     return 0;47 }48 ///公式n*(n+1)*(n+2)%p;49 ///两个 long long 的数直接相乘会爆long long;所以两两相乘

 

ZZNU 1988: Sn