Coffee and Buns
Problem's Link: http://www.bnuoj.com/v3/contest_show.php?cid=6415#problem/H
Mean:
给定两个数a和n，求[1,n]中有多少个x满足：gcd(4*(a+x),a^2+x^2)>1。
analyse:
gcd(4(a+x),a^2+x^2)>1 ----> gcd(a+x,(a+x)^2-2ax)>1 ----> gcd(a+x,2ax)>1 (gcd(a,b)=gcd(b,a%b)
假设a是偶数，那么gcd(a+x,2ax)>1 ----> gcd(a+x,ax)
设最大公约数为g，则g|ax，g|a+x
如果g|a，那么g|x，如果g|x，那么g|a，所以只要x是a任意一个因子的倍数就合法
假设a是奇数，那么有2种情况
1.x是奇数
2.x是a任意一个因子的倍数
所以要求1~maxn中与a，gcd > 1 的个数，就是求1~maxn与某一个num不互素的个数，要用到容斥原理。
Time complexity: O(N)
Source code:
;
;;
;) ;
;) p);
) ))));
}
/*
;;
;) ;
;) p);
) ))));
}
/*
*/