ZZNU 1988 （大数取余）
发布时间：2021-01-26 04:30:56 所属栏目：大数据 来源：网络整理
导读：1988: Sn 时间限制: 1 Sec?? 内存限制: 128 MB 提交: 19?? 解决: 8 [提交][状态] 题目描述 给你两个数 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组实例;
|
1988: Sn时间限制: 1 Sec??内存限制: 128 MB提交: 19??解决: 8 [提交][状态] 题目描述给你两个数 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 提示来源题意： 当然我们先得知道 1+3+6+10+15+.......的求和公式Sn=n*(n+1)*(n+2)/6; 所以这道题就是求：n*(n+1)(n+2)%p 当然没有那么简单 直接求会爆long long ； 这里运用了递归和同余定理的一些技巧：#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
ll Mul(ll a,ll b,ll p)
{
if(b==0)
return 0;
ll ans=2*Mul(a,b/2,p)%p;
if(b%2)
ans=(ans+a)%p;
return ans;
}
int main()
{
ll n,p;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&p);
ll ans=Mul(n+1,n,p);
ans=Mul(ans,n+2,p);
printf("%lldn",ans);
}
return 0;
}
（编辑：晋中站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
