Fork me on GitHub

Uoj#42.【清华集训2014】Sum

Uoj#42. 【清华集训2014】Sum

题意:

  • 给出$n,r$,求下面这个式子:

题解:

  • 显然只需要知道$\lfloor \sqrt{d^2\times r} \rfloor=\lfloor d\times \sqrt{r} \rfloor$的奇偶性即可。
  • 设$x=\sqrt{r},$$\lfloor d\times x \rfloor$为偶数意味着$\lfloor d\times x \rfloor=2\lfloor \frac{d\times x }{2}\rfloor$。
  • 也就是说$(-1)^{\lfloor d\times x \rfloor}=4\lfloor \frac{d\times x}{2} \rfloor-2\lfloor d\times x \rfloor+1$。
  • 所以$Ans=\sum\limits_{d=1}^{n}(4\lfloor \frac{d\times x}{2} \rfloor-2\lfloor d\times x \rfloor+1)$。
  • 之后我们考虑计算$\sum\limits_{d=1}^{m}\lfloor d\times y \rfloor$。
  • 如果$m\times y<1$,那么返回$0$。
  • 否则如果$y>1$,减去$y$整数部分的答案,即$\lfloor y \rfloor\times \frac{m(m+1)}{2}+\sum\limits_{d=1}^{m}\lfloor d\times (y-\lfloor y \rfloor) \rfloor$。
  • 如果$y<1$,返回$m\times \lfloor m\times y \rfloor-\sum\limits_{d=1}^{\lfloor m\times y \rfloor}\lfloor d\times \frac{1}{y} \rfloor$。
  • 似乎这个叫类欧几里得算法。
  • 复杂度$O(\log n)$。
  • 注意中间过程实数用$\frac{a\times \sqrt{r}+b}{c}$的形式存储。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
int n,r;
long double R;
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
struct ld
{
long long a,b,c;
ld(long long a=0,long long b=0,long long c=0):a(a),b(b),c(c){}
friend ld operator *(const ld &A,const long long &B)
{
return ld(A.a*B,A.b*B,A.c);
}
friend ld operator -(const ld &A,const long long &B)
{
return ld(A.a,A.b-A.c*B,A.c);
}
long double val()
{
return (long double)(a*R+b)/c;
}
long long Val()
{
return (long long)val();
}
};
ld rev(ld A)
{
long long a=A.a,b=A.b,c=A.c;
long long now=__gcd(__gcd(c*a,b*c),a*a*r-b*b);
return ld(c*a/now,-b*c/now,(a*a*r-b*b)/now);
}
long long S(long long n,ld d)
{
if ((d*n).val()<1) return 0;
if (d.val()<1) return (d*n).Val()*n-S((d*n).Val(),rev(d));
return (d.Val())*n*(n+1)/2+S(n,d-d.Val());
}
int main()
{
int T=read();
while (T--)
{
n=read(),r=read();
R=sqrtl(r);
int x=R+0.5;
if (x*x==r)
{
if (!(x&1)) printf("%d\n",n);
else if (n&1) puts("-1");
else puts("0");
}
else printf("%lld\n",(long long)n+4ll*S(n,ld(1,0,2))-2ll*S(n,ld(1,0,1)));
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#42.【清华集训2014】Sum

文章作者:wzf2000

发布时间:2018年04月18日 - 15:04

最后更新:2018年04月27日 - 11:04

原始链接:https://wzf2000.github.io/2018/04/18/Uoj42/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。