CF1389E Calendar Ambiguity 题解

分析

即求

(x-1)d + y \equiv (y-1)d + x \pmod w

满足 $x < y$ 的解 $(x,y)$ 的个数。

化简

xd + y \equiv yd + x \pmod w

yd - xd - x -y \equiv 0 \pmod w

(y-x)(d-1) \equiv 0 \pmod w

设 $w' = \frac{w}{\gcd(w,d-1)}$ ，那么有

y-x \equiv 0 \pmod {w'}

考虑 $y-x = k w'$ 。当 $k$ 为定值时，由于 $y-x \in [1,\min(d,m)]$ ，所以数量为 $\min(d,m) - kw'$ 。

答案即为

\sum_{k=1}^{\lfloor \frac{\min(d,m)}{w'} \rfloor} \min(d,m) - kw'

发现这是个等差数列，直接求和即可。

首项 $\min(d,m) - kw'$ ，末项 $\min(d,m) - \lfloor \frac{\min(d,m)}{w'} \rfloor w'$ ，公差 $\lfloor \frac{\min(d,m)}{w'} \rfloor$

答案

\frac{\big(2 \min(d,m) - \lfloor \frac{\min(d,m)}{w'} \rfloor w' - w'\big) \cdot \lfloor \frac{\min(d,m)}{w'} \rfloor }{2}

CODE

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int N=5e5+5;
5
int t, m, d, w;
6
int read() {
7
    int a=0, f=1; char c=getchar();
8
    while(!isdigit(c)) {
9
        if(c=='-') f=-1;
10
        c=getchar();
11
    }
12
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
13
    return a;
14
}
15
int gcd(int x,int y) { return y? gcd(y,x%y):x; }
16
void solve() {
17
    m=read(), d=read(), w=read();
18
    int ans=0;
19
    w/=(gcd(d-1,w));
20
    int mn=min(m,d), cnt=mn/w;
21
    ans=(2*(mn-w)-w*(cnt-1))*cnt/2;
22
    printf("%lld\n",ans);
23
}
24
signed main() {
25
    t=read();
26
    while(t--) solve();
27
}

Nanami^2

分析

CODE

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

分析

CODE

觉得这篇文章怎么样？

分享这篇文章

评论区