题解 P3910 【纪念邮票】

· · 题解

咳咳，某蒟蒻第二次发题解

第一次看这题内心OS：

哇哦，好水哦 又能混一道黄题了

于是噼里啪啦三重循环

然后 原地 爆炸

深思熟虑后改了双重循环

照样爆炸

仔细看了看题：10^9

当场吐血身亡

（一开始看成109）

被老师要求拿出纸和笔

开始写：

a是第一个数，b是最后一个数，len为长度

（a+b）* len / 2 = m (公式）

然鹅介里有两个变量，就意味着要两重循环

所以开始启动我们的 数 学 模 式

(咳咳，敲黑板）

因为len=b-a+1
所以b=len+a-1
那么式子就变成了（a+a+len-1)*len/2=m
然后移项 2a+len-1=2m/len
2a=2m/len-len+1
a=(2m/len-len+1)/2

那么，我们只要枚举len就好啦ヾ(◍°∇°◍)ﾉﾞ

代码：

#include<bits/stdc++.h>
using namespace std;
int m,n;
int main()
{
    cin>>n>>m;
    for(int i=n;i>=1;i--)
    {
                //当式子中的数不是整数或超出范围，就continue掉
        if((2*m)%i!=0)continue;
        if(((2*m/i)-i+1)%2!=0)continue;//不是整数

        int a=((2*m/i)-i+1)/2;

        if(a<1)continue;
        if(a+i-1>n)continue;//超出范围
        cout<<"["<<a<<","<<a+i-1<<"]"<<endl;
    }   
    return 0;   
}

兴高采烈的交上去(ﾉﾟ▽ﾟ)ﾉ

三个点TLE !!!∑(ﾟДﾟノ)ノ

_(:ι」∠)_心态爆炸

只好去问大佬

得出：查找范围应该在 2m½ 范围内（根号打不出来QAQ随意吧）

最终代码 ：

↑↑↑ i=n改成i=sqrt（2*m）就好了

（你以为我会给你直接抄的机会吗哈哈哈不可能的）

(o°ω°o)管理员大大求过