题目大意

题意

分析

根据题意易列出同余式

(y−1)∗d+x≡(x−1)∗d+y(mod w)(y-1)*d+x \equiv (x-1)*d+y \quad (mod \ w)

化简得

x∗(d−1)≡y∗(d−1)(mod w)x*(d-1) \equiv y*(d-1) \quad (mod \ w)

令 k=gcd( (d−1) , w )k = gcd( \ (d-1) \ , \ w \ )

则 x≡y(mod w/k)x \equiv y \quad (mod \ w/k)

这样分模数讨论即可且根据题意可知 x<y<=min(m,d)x < y <= min(m,d)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve(){
    int m,d,w;
    cin>>m>>d>>w;
    int k = min(m,d);
    int res = 0;
    if((d-1) % w == 0){
        res = k*(k-1)/2;
    }
    else{
        int g = __gcd(w,d-1);
        w = w / g;
        int d = k / w;
        int dx = k - (k/w*w);
        res = d*(d+1)/2*dx + (d-1)*d/2*(w-dx);
    }
    cout << res << endl;
}