CF1146D Frog Jumping
题目描述
A frog is initially at position 00 on the number line. The frog has two positive integers aa and bb . From a position kk , it can either jump to position k+ak+a or k-bk−b .
Let f(x)f(x) be the number of distinct integers the frog can reach if it never jumps on an integer outside the interval [0, x][0,x] . The frog doesn't need to visit all these integers in one trip, that is, an integer is counted if the frog can somehow reach it if it starts from 00 .
Given an integer mm , find \sum_{i=0}^{m} f(i)∑i=0*m**f(i) . That is, find the sum of all f(i)f(i) for ii* from 00 to mm .
输入格式
The first line contains three integers m, a, bm,a,b ( 1 \leq m \leq 10^9, 1 \leq a,b \leq 10^51≤m≤109,1≤a,b≤105 ).
输出格式
Print a single integer, the desired sum.
题意翻译
yyb大神仙在数轴的00位置。yyb大神仙有两个正整数a,ba,b，如果当前yyb大神仙在位置kk，yyb大神仙可以用神仙的力量将自己传送到k+ak+a或者k-bk−b位置。
但是yyb大神仙感觉这样很无聊所以打算将自己限制在一段区间里。f(x)f(x)表示yyb大神仙只能在[0,x][0,x]区间里移动，从00开始能到达的整点数量。yyb大神仙想求\sum_{i=0}^mf(i)∑i=0*m**f(i*)。
输入输出样例
输入 #1复制
输出 #1复制
输入 #2复制
输出 #2复制
输入 #3复制
输出 #3复制
输入 #4复制
输出 #4复制
说明/提示
In the first example, we must find f(0)+f(1)+\ldots+f(7)f(0)+f(1)+…+f(7) . We have f(0) = 1, f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 1, f(5) = 3, f(6) = 3, f(7) = 8f(0)=1,f(1)=1,f(2)=1,f(3)=1,f(4)=1,f(5)=3,f(6)=3,f(7)=8 . The sum of these values is 1919 .
In the second example, we have f(i) = i+1f(i)=i+1 , so we want to find \sum_{i=0}^{10^9} i+1∑i=0109i+1 .
In the third example, the frog can't make any jumps in any case.
题解：
2019.10.28模拟赛T2 60分场
出题人@Winniechen的数据挺良心的（滑稽）
我很疑惑，为什么大佬们一开始都能想到找规律出正解。我一开始只能想到深搜，所以用一个差不多是\(O(n^2)\)的算法拿了\(10^3\)的分，假如数据是按上面说的：\(10^9\)，这个算法得跑31年...
先贴一份代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn=1e5+10;
int n,a,b,cnt,ans;
bool v[maxn];
void dfs(int pos,int l)
{
if(pos<0 || pos>l || v[pos])
return;
v[pos]=1;
cnt++;
dfs(pos+a,l);
dfs(pos-b,l);
}
signed main()
{
scanf("%lld%lld%lld",&n,&a,&b);
for(int i=0;i<=n;i++)
{
cnt=0;
memset(v,0,sizeof(v));
dfs(0,i);
ans+=cnt;
}
printf("%lld",ans);
return 0;
}这就是编程的魅力，一再优化，你的31年，人家的一秒，这就是差距。国家实力就是这么被提升起来的。
接下来介绍正解：
根据我们手推样例，不难发现，会有一个路径让我们返回到出发点，这样的话就会开始循环跳来跳去。（其实这是我深搜的时候发现的），所以我们会发现一个性质：在一个区间中，如果有一个点能到达，那么这个点一定是\(\gcd(a,b)\)的倍数。
证明其实也好证：
假设我们向右跳了\(x\)次，向左跳了\(y\)次。那么就会存在一个点\(k\)：
\[
ax+by=k
\]
显然\(k\)一定是\(\gcd(a,b)\)的倍数。
那我们回头来求这个函数\(f(i)\)，不难看出，当\(a>i\)的时候，总和就是\(a\)，因为根本就动弹不了。
所以当\(n<a\)的时候就输出\(n+1\)即可（加的那个\(1\)代表\(f(0)\)）。
否则我们一次性在答案上加\(a\)（一次性累加\(f(0)-f(a-1)\)）。
然后我们在\([a,i]\)这个区间上寻找一个可以让路径回到出发点的点\(k\)，这样的话我们就相当于处理出了一个临界值，之后的东西可以用刚才我们推出的规律处理。这个处理过程其实是一个模拟的过程，先一直往右跳，再一直往左跳，什么时候正好跳回来了就标记上（这个省略了标记的步骤，因为直接拿\(i\)记录了），最后加上跳跃的次数。
很显然，这种一次枚举跳很多步的时间复杂度是很优秀的。
这个时候跳出循环，然后按照我们发现的规律：所有可被到达的点都是\(\gcd(a,b)\)的倍数。这样处理出其他的点到\(n\)的情况。进行累加答案，输出即可。
代码：
#include<cstdio>
#define int long long
using namespace std;
int n,a,b,pos,i;
int ans,tmp=1;
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
signed main()
{
scanf("%lld%lld%lld",&n,&a,&b);
ans+=a;
if(n<a)
{
printf("%lld",n+1);
return 0;
}
for(i=a;i;i++)
{
while(pos+a<=i)
{
tmp+=((i-pos)/a);
pos+=((i-pos)/a)*a;
tmp+=(pos/b);
pos%=b;
if(!pos)
break;
}
if(!pos)
break;
ans+=tmp;
if(n==i)
break;
}
if(!pos)
{
int p=gcd(a,b);
int j=n-n%p;
tmp=(int)(i+j)*(j/p-i/p+1)/2;
tmp-=(int)(j+p-1-n)*(j/p);
ans+=tmp+n-i+1;
}
printf("%lld",ans);
return 0;
}