bestcoder round 80

2つの水問題を切ったが,hackが5つあったおかげで100余り増えた.
Lucky  
 Accepts: 819
 
 Submissions: 2299
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
問題の説明

\ \ \ \    Vampire    ,          .

\ \ \ \            S,    S         S               (          ).

\ \ \ \            ,                  ,  ”YES”,    ”NO”.

説明の入力

\ \ \ \            T,     .

\ \ \ \             n,      .

\ \ \ \       n  ,        .

\ \ \ \ 1\le n\le 10^5,1\le T \le 10,0\le a_i \le 10^9    1≤n≤10​5​​,1≤T≤10,0≤a​i​​≤10​9​​.

出力の説明

\ \ \ \            ”YES” ”NO”.

入力サンプル

1
1
2

出力サンプル

NO

题目はたくさん言って、実は配列の中で0と1があるかどうかを判断するだけで、コードは略...
Segment  
 Accepts: 418
 
 Submissions: 2020
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
問題の説明

\ \ \ \    Rivendell   ,         .

\ \ \ \                 .      x+y=qx+y=q,                   ,                       .

\ \ \ \                            ,       PP      .

説明の入力

\ \ \ \          T,       .

\ \ \ \             qq,PP,        .

\ \ \ \ q    q    q\le 10^{18},1\le P\le 10^{18},1\le T \le 10q≤10​18​​,1≤P≤10​18​​,1≤T≤10.

出力の説明

\ \ \ \         ,       PP   .

入力サンプル

1
2 107

出力サンプル

0

図を描くと式は(q-1)(q-2)/2になりますが、qは10^18あり、直接二乗すると爆発するので、高速べき乗を使いますが、先算(q-1)(q-2)なのでしょうか.modが過ぎた数はこれ以上除くことができないでしょう.
だから解決策はまず偶数を探して2を除いて、それから高速べき乗の形式で乗算します(私はそれを高速と言います)

#include<cstdio>
#include<iostream>
using namespace std;
int t;
long long q,p,x,y,ans;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>q>>p;
		x=q-1;
		y=q-2;
		if(x%2==0) x=x/2;else y=y/2;
		ans=0;
		while(x!=0)
		{
			if(x%2==1) ans=(ans+y)%p;
			x=x>>1;
			y=(y<<1)%p;
		}
		cout<<ans<<endl;
	}
}