2017|[BZOJ3817][Sum][类欧几里得算法数论] 数论|类欧几里得算法|oi|数论

题目大意：给定 N<=109,R<=104 ，求：

∑d=1n(?1)?d?r?d√?
思路：不妨设 x=r√ ，那么

?1?dx?=1?2(?dx?%2)=1?2(?dx???dx2??2)=1+4?dx2?+2?dx?
所以：

∑d=1n=n+4∑d=1n?dx2??2∑d=1n?dx?
考虑表达式的一般形式：

∑i=1n?abx+ci?=∑i=1n?ki?
当 k>=1 时：

=∑i=1n(?bx+ca?+bx+c??bx+ca?aa)i=∑i=1n(bx+c??bx+ca?aa)i+?bx+ca??C2n
当 k<1 时：
【2017|[BZOJ3817][Sum][类欧几里得算法数论]】
=?kn?n?∑j=1kn?abx?acb2v?c2?j?

发现新的表达式和原表达式形式类似，因此可以递归求解，辗转的过程类似于欧几里得法求 gcd ，因此被称为类欧。
考虑它的几何意义，相当于是求一个斜边为 y=kx 直角三角形内整点的个数，这个过程相当于把三角形不停翻转。
因为 k>=1 和 k<1 必定是轮流出现，所以这两步可以在一步内完成。
为什么用cin读入会RE？？？

代码：

#include using namespace std; typedef long long ll; ll T, n, m; double t; inlinell gcd(ll a, ll b) { if (!b) return a; return gcd(b, a % b); } inline ll calc(ll n, ll a, ll b, ll c) { if (!n) return 0; ll g = gcd(gcd(a, b), c); a /= g, b /= g, c /= g; ll k = (t * b + c) / a, ret = n * (n + 1) / 2 * k; c -= k * a; k = (t * b + c) / a * n; ret += n * k; ret -= calc(k, b * b * m - c * c, a * b, -a * c); return ret; } int main(void) { //freopen("in.txt", "r", stdin); scanf("%lld", &T); while (T--) { scanf("%lld%lld", &n, &m); t = sqrt(m); if ((ll)t == t) printf("%lld\n", (ll)((m & 1) ? ((n & 1) ? -1 : 0) : n)); else printf("%lld\n", n + (calc(n, 2, 1, 0) << 2) - (calc(n, 1, 1, 0) << 1)); } return 0; }

完。
By g1n0st