Wuyanru's blog
0%

[清华集训 2014] Sum

发表于 分类于 ，

你的注意力有一些松弛，但是你的……

题目链接。

题意

给定 ，求 。

，，数据组数 。

题解

发现当 为整数的时候有 。

那么有 。

而我们知道 。

所以就可以得到 。

那么设 。

则答案为 。

那么如果我们能求出这个 的值，问题就结束了。

设 。

首先我们特判掉 是有理数的情况，则对于剩下的情况 一定是无理数。

当 时

设 ，那么：

当 时

如果记得类欧板子怎么推，那么这里应该比较简单。

设 。 等等，我们为什么要分情况讨论……

不难发现，因为如果 ，那么一定有 ，这样才能保证递归可以结束。

复杂度，不会证，我也没有在别的地方看到复杂度证明，可能是我蠢了？

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
66
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll gcd(ll a,ll b)
{
    ll r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
ld sr;int r;
ll f(ll a,ll b,ll c,ll n)
{
    if(!n) return 0;
    ll g=gcd(a,gcd(b,c));
    a/=g,b/=g,c/=g;

    ld t=(a*sr+b)/c;ll V=floor(t);
    if(V) return n*(n+1)/2*V+f(a,b-V*c,c,n);
    ll m=floor(t*n);
    return n*m-f(a*c,-b*c,a*a*r-b*b,m);
}
int main()
{
    int T=read();
    while(T--)
    {
        int n=read();r=read();sr=sqrtl(r);
        int v=floor(sr+0.5);
        if(v*v==r)
        {
            if(v%2==0) printf("%d\n",n);
            else if(n&1) printf("-1\n");
            else printf("0\n");
        }
        else printf("%lld\n",n-2*f(1,0,1,n)+4*f(1,0,2,n));
    }
    return 0;
}

感谢观看！