首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。