The game is played by Alice and Bob. Initially, there are $n$ stones.
The players alternate turns, making a move described below, with Alice going first. The player who becomes unable to make a move loses.
- In Alice's turn, she must remove a number of stones that is a positive multiple of $A$.
- In Bob's turn, he must remove a number of stones that is a positive multiple of $B$.
In how many of Game $1$, Game $2$, ..., Game $N$ does Alice win when both players play optimally?
Constraints
- $1 \leq N ,A,B \leq 10^{18}$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $A$ $B$
Output
Print the answer.
Sample Input 1
4 2 1
Sample Output 1
2
In Game $1$, Alice cannot make a move and thus loses.
In Game $2$, Alice removes $2$ stones, and then Bob cannot make a move: Alice wins.
In Game $3$, Alice removes $2$ stones, Bob removes $1$ stone, and then Alice cannot make a move and loses.
In Game $4$, Alice removes $2 \times 2 = 4$ stones, and then Bob cannot make a move: Alice wins.
Therefore, Alice wins in two of the four games.
Sample Input 2
27182818284 59045 23356
Sample Output 2
10752495144
所以问题转化为有多少个 \(x\in[A,n]\) 满足 \(x \bmod A<b\)
把 \([A,n]\) 的数按照 \(\bmod A\) 的余数分组，每 \(A\) 个为一组。那么共有 \(\left\lfloor\frac{n-A}{A}\right\rfloor\) 个完整的组。每一组里面有 \(\min(a,b)\) 个合法的数。剩下的 \(n \bmod A +1\) 个数里面又有 \(\min(n\bmod A+1,b)\) 个合法的数。我们就可以 \(O(1)\) 求出答案。
注意特判 \(n<A\)
#include<bits/stdc++.h>
#define ll long long
#define p1 998244353
#define p2 1000000007
using namespace std;
ll n,a,b,ans;
int main()
{
scanf("%lld%lld%lld",&n,&a,&b);
if(n<a) printf("0");
else{
n-=a;
ans+=n/a*min(a,b);
n-=n/a*a;
printf("%lld\n",ans+min(n+1,b));
}
return 0;
}