Sweet

题目：Sweet
来源：第二届太原理工大学程序设计新生赛决赛（重现赛）

解题思路

幼稚园有n个小幼稚，编号1~n由左至右，站成一排。幼稚长从左向右发糖果，每a个小幼稚获得一个糖果（a号是第一个得到糖果的），从右往左发饼干，每b个小幼稚获得一个饼干（(n-b+1)号是第一个得到饼干的）。 幼稚长想要知道有多少小幼稚既获得了糖果又获得了饼干。

获得糖果的小幼稚：a, 2*a, 3*a, 4*a, ...，编号是 a 的倍数。
从左往右，第一个获得饼干的小幼稚为 i = n % b + 1。遍历 i，记录从左往右第一个同时获得糖果和饼干的小幼稚 i，cnt = 1。
计算 a 和 b 的公倍数 num = a * b / __gcd(a,b)，
那么从现在的 i 开始，每 num 个小幼稚，就会同时获得糖果和饼干。
所以，i 后面还有 (n-i)/num 个小幼稚同时获得糖果和饼干。

C++代码

#include<iostream>
#include<algorithm>
using namespace std;

long long n, a, b;

long long getTwo(){
    long long cnt = 0;
    if(a > n || b > n)
        return 0;
    if(b == 1){
        cnt = n / a;
        return cnt;
    }
    if(a == 1){
        cnt = n / b;
        return cnt;
    }

    long long i = n % b + 1;    //从左到右第一个获得饼干的小朋友
    if(a == b && i%a != 0)
        return 0;
    long long k = __gcd(a, b);
    if(k == a && i%a != 0)
        return 0;
    if(k == b && a%i != 0)
        return 0;

    long long num = a / k * b;
    for(; i<=n; i+=b){
        if(i % a == 0){
            ++cnt;
            break;
        }
    }
    if(i > n)
        return 0;

    cnt += (n-i) / num;    // 此时，i 是从左到右第一个同时获得糖果和饼干的小朋友
    return cnt;
}

int main(){
    cin >> n >> a >> b;
    long long cnt = getTwo();
    cout << cnt << endl;
    return 0;
}