2019-4-24-div2 非常自闭的一场div2

题目连接 : cf

A. Neko Finds Grapes

待补ing

B. Neko Performs Cat Furrier Transform

待补ing

C. Neko does Maths

Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers aa and bb. His goal is to find a non-negative integer kk such that the least common multiple of a+ka+k and b+kb+k is the smallest possible. If there are multiple optimal integers kk, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?

c题该怎么说很迷,哪怕理解大致思路了,其实c题是这个意思因为求的是lcm(a + k, b + k)这个东西,其实我刚开始是选择放弃的,不过看到d题的树形dp我还是回到了这道题,比赛的时候WA了两发,比赛结束后推了一个半小时作业才推出了,为了让我明天来看还能明白思路,所有抓紧写上思路,

首先是差值,为什么要确定差值呢,一位daolao是这样说的"因为差是不变的"

正是因为差是不变的才能根据差得到一个k,使其lcm最小

所以我们为什么要枚举k的因数,因为假设y = lcm(a,b);那么易证abs(a - b)|y,所以说若非是k的因数,那样加起来会凑成互质的情况,那样lcm肯定会很大然后枚举i = 1~sqrt(abs(a - b))使其从i和 abs(a - b) / i中寻找答案,我都处理是将其全部计算其中k = (i - a % i)  %  i然后开一个容器存起来lcm和k的值

然后排序一遍即可。至于为什么k = (i - a % i)  %  i,这个就是将i转化成b-a的倍数。

code:(不过叫这个代码会WA再第5个点,但是这个代码是正确的,我就是用这份代码AC的)

int a, b; cin >> a >> b;
    if(a > b) swap(a, b);
    int c = b - a;
    vector<int> u;
    for(int i = 1 ; i * i <= c ; i ++)
    {
        if(c % i == 0)
        {
            u.push_back(i);
            if(i * i != c) u.push_back(c / i);
        }
    }
    vector<pair<ll, int> > e;
    for(auto x : u)
    {
        x = (x - (a % x)) % x;
        ll lcm = (a + x) * (b + x) / gcd(a + x, b + x);
        e.push_back(pair<ll, int>(lcm, x));
    }
    sort(e.begin(), e.end());
    cout <<e[0].second << endl;

D. Neko and Aki's Prank

待补ing(ps:不一定能做出来)

E. Neko and Flashback

待补ing(ps:不一定能做出来)

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注