yukicoder No.442 和と積

問題はこちら
No.442 和と積 - yukicoder

A*Bが64bitに収まらないので、多倍長を持ち出すか、なんか考えないといけない
D=gcd(A,B)とし、A=Da、B=Dbとする。ここでa,bは互いに素となる。
gcd(A+B,AB)=gcd(D(a+b),DDab)=D*gcd(a+b,Dab)
であり、a,bが互いに素であることからa+bとabは互いに素
（なぜなら、abの任意の素因数pはa,bのちょうど一方のみを割り切るので、a+b mod pは0+非0より非0、すなわちa+bはpを因数に持たない）
よってDabのうち、a+bと1より大きな共通因数を持ちうるのはDの部分のみなので、gcd(a+b,Dab)=gcd(a+b,D)
これにより、64bitの範囲で計算できることがわかった。

なお、gcdと整序関係の一般論で殴ると多分こんな感じ
＝＝＝
一般に、整数x,y,z,wとd≠0に対し次が成立する
(1) gcd(x,yz)|gcd(x,y)gcd(x,z)
(2) gcd(x+y,x)=gcd(x+y,y)=gcd(x,y)
(3) (x|y かつ z|w) ⇒ xz|yw
(4) (x|y かつ gcd(y,z)|x) ⇒ gcd(y,z)=gcd(x,z)
(5) (x|y かつ x|z) ⇒ x|(y+z)
(6) (d|x かつ d|y) ⇒ gcd(x,y)=d*gcd(x/d,y/d)
が成立する
（(2)は互除法。(5)は明らか。それ以外は、各素因数の指数について、gcdがmin、積が+、整序関係が≦と対応していることから従う）
(1)より gcd(A+B,AB)|gcd(A+B,A)gcd(A+B,B)
(2)より gcd(A+B,A)gcd(A+B,B)=gcd(A,B)^2
(3)より gcd(A,B)^2 | AB
これらと(4)より gcd(A+B,AB)=gcd(A+B,gcd(A,B)^2)
(5)より gcd(A,B)|(A+B)
これらと(6)よりgcd(A+B),AB)=gcd(A,B)gcd( (A+B)/gcd(A,B),gcd(A,B) )
＝＝＝
（※「gcd(a,b)=1⇒gcd(a+b,ab)=1も上の(1)(2)から従う）

あとは実装するだけ

long gcd(long p,long q){return q?gcd(q,p%q):p;}

int main(){
	long a,b,d;
	scanf("%ld%ld",&a,&b);
	d=gcd(a,b);
	printf("%ld",d*gcd(a/d+b/d,d));
	return 0;
}

適当に縮める

long g(long p,long q){return q?g(q,p%q):p;}
long a,b,d;
main(){
	scanf("%ld%ld",&a,&b);
	a=!printf("%ld",d*g(a/d+b/d,d=g(a,b)));
}

123B
いい感じの短縮が思いつかない