洛谷P3764 签到题 III

题目背景

pj组选手zzq近日学会了求最大公约数的辗转相除法。

题目描述

类比辗转相除法，zzq定义了一个奇怪的函数：

typedef long long ll;
ll f(ll a,ll b)
{
    if(a==b) return 0;
    if(a>b) return f(a-b,b+b)+1;
    else return f(a+a,b-a)+1;
}

zzq定义完这个函数兴高采烈，随便输入了两个数，打算计算f值，发现这个函数死循环了...于是zzq定义这个函数递归死循环的情况下f值为0。

现在zzq输入了一个数n，想要求出 $sum_{i=1}^n sum_{j=1}^n f(i,j)$ 。

输入输出格式

输入格式：

一行两个数n。

输出格式：

一行一个数 $sum_{i=1}^n sum_{j=1}^n f(i,j)$ 。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

说明

对于10%的数据， $n leq 300$ 。

对于40%的数据， $n leq 2000$ 。

对于70%的数据， $n leq 5 imes 10^5$ 。

对于100%的数据， $1 leq n leq 5 imes 10^{11}$ 。

数学问题结论题分块

似乎很有趣。

要证一个奇奇怪怪的结论：

当且仅当 “ $ a/(gcd(a,b)+b/gcd(a,b)=2^m $ ”时， $ f(a,b) $ 值为 $ m-1 $ ，否则 $ f(a,b)=0 $

一种简单的证明如下：

打表观察，发现上述结论显然成立，得证

另一种并不严谨的证明如下：

只考虑gcd(a,b)=1的情况

证明： $ a+b=2^m $时，$ f(a,b)=m-1 $

当 $a=1$ $b=1$ $ a+b=2^1 $时，显然有$ f(a,b)=1-1=0 $

否则，对于任意 $ a+b=2^m $，假设a<b，那么 $ f(a,b)=f(a+a,b-a)+1 $

由于a+b是2的倍数且a,b互质且a<b，那么b-a肯定是偶数，所以 $ f(a+a,b-a)=f(a*2,b-a)=f(a,(b-a)/2) $

此时$ a+(b-a)/2 = 2_{ }^{m-1} $ ，递归计算可得 $ f(a,b)=m-1 $ 得证。

其他情况乱搞一下发现会死循环

然后愉快（并不）地分块求值。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #define LL long long
 7 using namespace std;
 8 const int mxn=100010;
 9 LL read(){
10     LL x=0,f=1;char ch=getchar();
11     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}
13     return x*f;
14 }
15 LL n,ans=0;
16 int main(){
17     n=read();
18     int lg=0;
19     for(LL i=2;i;i<<=1){
20         for(LL x,j=(i>>1)+1;j<i && j<=n;j=x+2){
21             x=n/(n/j);
22             x=min(x,min(n,i-1));
23             if(!(x&1))x--;
24             ans+=lg*(n/j)*(((x-j)>>1)+1);
25         }
26         if(i>=n)break;
27         ++lg;
28     }
29     ans<<=1;
30     printf("%lld
",ans);
31     return 0;
32 }