题解 P3951 【小凯的疑惑】

Sky_crystal · 2017-12-14 09:38:27 · 题解

我们可以把所有的数根据%a余数的不同来分成a类

在数轴上，就是把数轴截成长度为a的无数段

假设每个可以表达出来的数为k=x*a+y*b

考虑枚举b的个数

显然，当a的个数改变的时候k%a的值是不会变的

体现到数轴上，就是a的数量增大时，在划分出的区间中是同一个位置

之后把b的数量+1，后面这一段上有一个位置被覆盖了

显然每次都会覆盖一个新的位置（否则出现循环，答案不存在）

于是，当第a-1次覆盖的时候这一段里面的a-1个空位恰好被全部覆盖一遍，这个位置的数为(a-1)*b

当前这一段为第一个被完全覆盖的段

在它之前的一段，与最后一次覆盖相对应的位置没有被覆盖

也就是(a-1)*b-a，整理得a*b-a-b.

#include<bits/stdc++.h>
long long a,b;
int main()
{
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",(a-1)*b-a);//其实就是a*b-a-b
    return 0;
}

---------分割线----------

这是我考场上推出的SB式子…… 最后五分钟突然意识到写的O(N)算法可以变成O(1)于是就……

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
long long a,b,ans,sum,t;
int main()
{
    scanf("%lld %lld",&a,&b);
    if (a>b)swap(a,b);
    t=(a-1)*b/a-1;
    sum=(sum+(a-1)*b)%a;
    printf("%lld",t*a+sum);
    return 0;

}