题目背景
pj组选手zzq近日学会了求最大公约数的辗转相除法。
题目描述
类比辗转相除法,zzq定义了一个奇怪的函数:
typedef long long ll;
ll f(ll a,ll b)
{
if(a==b) return ;
if(a>b) return f(a-b,b+b)+;
else return f(a+a,b-a)+;
}
zzq定义完这个函数兴高采烈,随便输入了两个数,打算计算f值,发现这个函数死循环了...于是zzq定义这个函数递归死循环的情况下f值为0。
现在zzq输入了一个数n,想要求出。
输入输出格式
输入格式:
一行两个数n。
输出格式:
一行一个数。
输入输出样例
100
1124
2000
68204
说明
对于10%的数据,。
对于40%的数据,。
对于70%的数据,。
对于100%的数据,。
数学问题 结论题 分块
似乎很有趣。
要证一个奇奇怪怪的结论:
当且仅当 “ $ 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 $ 得证。
其他情况乱搞一下发现会死循环
然后愉快(并不)地分块求值。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int mxn=;
LL read(){
LL x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
LL n,ans=;
int main(){
n=read();
int lg=;
for(LL i=;i;i<<=){
for(LL x,j=(i>>)+;j<i && j<=n;j=x+){
x=n/(n/j);
x=min(x,min(n,i-));
if(!(x&))x--;
ans+=lg*(n/j)*(((x-j)>>)+);
}
if(i>=n)break;
++lg;
}
ans<<=;
printf("%lld\n",ans);
return ;
}