[CodeChef FEB15]Payton numbers(CUSTPRIM)解题报告

题目

https://www.codechef.com/problems/CUSTPRIM

（翻译来自洪华敦）

定义三元组的乘法

def multiply((a1,b1,c1), (a2,b2,c2)):

s = (a1a2 + b1b2 + c1c2) + (a1b2 + b1a2) + (c1 + c2)

t = floor[s/2] + 16(c1 + c2) – c1c2

A = (t – 2(a1b2 + b1a2) – (a1c2 + c1a2) + 33(a1 + a2)+ (b1b2 – a1a2))

B = (t – 5(a1b2 + b1a2) – (c1b2 + b1c2) + 33(b1 + b2)+ (2b1b2 + 4a1a2))

if s is even: return (A-540,B-540,24)

else: return (A-533,B-533,11)

定义zero：若x*任何y=0，则称x是zero

定义单位元，若x*任何y=y，则称x是单位元

定义质数，若x不是zero且不能分解成两个非单位元的乘积，则称x是质数

给定一个三元组，问他是不是质数

题解

CC上有自带的（英文）题解：

https://discuss.codechef.com/questions/64621/custprim-editorial

还有一篇中文翻译：

http://pan.baidu.com/s/1hqsF3Sw

翻译有遗漏之处，以原文为准。反正我就是看CC上的英文题解看懂的。

解法简直出(sang)神(xin)入(bing)化(kuang)，大家还是去看原文吧……

（没错这真的是一篇解题报告）

代码

#include
#include
#include
#include
using namespace std;
typedef long long LL;
LL realmod(LL a,LL m){
	a%=m;
	if(a<0) a+=m;
	return a;
}
inline LL quickmul(LL x,LL y,LL MOD){
	x=realmod(x,MOD),y=realmod(y,MOD);
	return ((x*y-(LL)(((long double)x*y+0.5)/MOD)*MOD)%MOD+MOD)%MOD;
}
LL quickpow(LL a,LL n,LL M){
	a=realmod(a,M);
	LL ans=1;
	while(n){
		if(n&1) ans=quickmul(ans,a,M);
		a=quickmul(a,a,M);
		n>>=1;
	}
	return ans;
}
LL Legendre_symbol(LL a,LL p){//p是奇素数 
	//1代表a是平方剩余,-1代表a不是平方剩余,0代表a=0 
	//a^((p-1)/2)
	a=realmod(a,p);
	LL flg=quickpow(a,(p-1)/2,p);
	if(flg==0||flg==1) return flg;
	if(flg==p-1) return -1;
}
bool Rabin_Miller(LL n,LL p){//合数返回0
	if(n==2) return true;
	if(n==1||(n&1)==0) return false;
	LL d=n-1;
	while(!(d&1)) d>>=1;
	LL m=quickpow(p,d,n);
	if(m==1) return true;
	while(d

题目

题解

代码

发表回复 取消回复

发表回复取消回复