题解 P5436 【XR-2】 缘分

话说这道题嘛,一开始,我是想开启求最小公倍数的,但是……

肯定超时!

一个一个模拟的话,最多要枚举

$10^{18}× \times ×100$ 次!

不超时才怪!!

诶,我突然想到,最大的两个数求最小公倍数不就行了?

可是它们的最小公倍数不就是 nnn 了吗?

所以,要使得两个数的最小公倍数最大,就要两数互质 。

哦,既然这样,数学老师教过我们,相邻的两个自然数一定互质,所以 ……

只要求 nnn 和 n−1n-1n−1 的最小公倍数不就行了吗?

又由于两数一定互质,故它们的最小公倍数就是它们的乘积 。

但是,交上去怎么……

题解 P5436 【XR-2】 缘分

错的,全错!

为什么?

于是,我随手试了几个样例,就像:

111

111

出来的结果让我大吃一惊:

000

这就是问题所在!

所以,加一个特判就可以解决问题了:

if(n==1)
    printf("1");

下面放出完整代码:

 #include<bits/stdc++.h>
#define ll long long//定义long long
using namespace std;
ll n,t,i;//不开long long两行泪
ll read(){//相信大家都知道这就是大名鼎鼎的快读,我的其他博文内有介绍
    ll r=0,f=1;
    char c=getchar();
    while((c<'0'||c>'9')&&c!='-')
        c=getchar();
    if(c=='-')
        f=-1,c=getchar();
    while(c<='9'&&c>='0')
        r=r*10+c-'0',c=getchar();
    return r*f;
}
int main(){
    t=read();
    n=read();
    if(n==1)
        printf("1");
    else
        printf("%lld",n*(n-1));
    for(i=2;i<=t;i++){
        n=read();
        if(n==1)
            printf("\n1");
        else
            printf("\n%lld",n*(n-1));
    }
    return 0;
}

不过,相信大家也看到了,我定义 longlonglong longlonglong 是:

#define ll long long

在这里推荐一种更广为人知的写法:

typedef long long ll;

好了,就讲到这里,相信大佬们都明白了吧!

OIOI 加油!洛谷冲鸭!

上一篇:通过建站学运维(课时3)


下一篇:【XR-3】小道消息(数论)