codeforces-Ed92-E

E. Calendar Ambiguity

题意

给出一种日历进制 一年有m个月 每个月有d天 一个星期有w天

问该日历进制下有多少数对(x,y) x月y日和y月x日在一个星期的同一天

如上图同一列的红圈表示数对(x,y) 符合题意描述

题解:

这个问题用数学语言描述则为

$((x-1)×d+y)mod w =((y-1)×d+x)mod w$

整理式子得到

$(x-y)(d-1)=0 (mod w)$

即求有多少对(x-y)能使(x-y)(d-1)为w的倍数

由于(d-1)与w为定值可以先约分化简

得到$w’=w/gcd(w,d-1)$

那么现在就是求有多少数对(x,y)满足$(x-y)=0 (mod w’)$,或者说$(x-y)=kw’$

x月y日和y月x日必须合法所以: x and y <min(m,d)

然后考虑计数有多少对(x,y),假设k=1,那么有

x={1,2,3,…min(m,d)-w’}

y={1+w’,2+w’,…..min(m,d)}

共$min(m,d)-1×w’$对

同理统计$k=2,3,..,min(d,m)/w’$,k有min(d,m)/w’个值,

令$up=min(d,m)$,$num=up/w’$,那么用等差数列求和得到答案为

$ans=num ×up-num×(1+num)×w’/2$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e3+5;
const double Pi=acos(-1);

/*
*/

int main(){
    Turnoff;
    int t;cin>>t;
    while(t--){
        ll m,d,w;
        cin>>m>>d>>w;
        ///(x-y)(d-1)mod w=0
        w/=__gcd(d-1,w);
        ll up=min(d,m);
        ll num=up/w;
        cout<<(num*up-num*(1+num)/2*w)<<endl;
    }
}