Educational Codeforces Round 92 (Rated for Div. 2) E. Calendar Ambiguity

题目链接:http://codeforces.com/contest/1389/problem/E

大概题意:某个国家一年有m个月,每个月有d天,一个星期有w天。(x,y)且(x<y),表示x月y天,如果x月y天和y月x天是一周中的同一天,则(x,y)是好的,问你第一年中有多少个好的。

思路:a月b号和b月a好如果是一周的同一天,那(b-1)*d+a-( (a-1)*d+b)取模w要为0才行,化简得 (b-a)(d-1) 取模w要为0,设c=b-a,c为两个月份之差,那c*(d-1)%w==0,先让(d-1)取模下w, x=(d-1)%w; 如果x=0的话,那c为任意正整数都可以 ,那ans=md*(md-1)/2, md=min(m,d)。m和d要取个最小的,比如m=10,d=7,有10月7号,但没有7月10号,(我就是忘取最小的了,样例都过不了,我还以为其他地方有bug)。如果x!=0,那c只要是 lcm(w,x)/x 的正整数倍即可,设y=lcm(w,x)/x,那ans=(md-1)/y + (md-2)/y + (md-3)/y+........。然后再处理下这个就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fun(ll x,ll y)
{
    while(y)
    {
        ll z=x%y;
        x=y;
        y=z;
    }
    return x;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        ll m,d,w;
        cin>>m>>d>>w;
        ll md=min(m,d);//月数和每月的天数要取较小的
        ll x=(d-1)%w;
        if(x==0)//月份之差可以为任意正整数
        {
            cout<<md*(md-1)/2<<endl;
            continue;
        }
        ll y=x*w/fun(w,x);//最小公倍数
        y=y/x;//月份之差必须为y的倍数


        //答案就是 (md-1)/y + (md-2)/y + (md-3)/y+........
        
ll xx=(md-1)/y;
ll yy=xx-1; ll ans=yy*(yy+1)/2; ans*=y; ll zz=(md-1)%y; zz++; ans=ans+xx*zz; cout<<ans<<endl; } }

  

上一篇:用三种不同颜色表示的三个决策边界


下一篇:一个商业分析师对于工作的YY