Codeforces

Luogu

分析

神仙构造题?

首先可以发现,当 $x<10^{18}$ 时有这样一个关系式

$$ f(x+10^{18})-f(x)=1 $$

也就是说,当 $[l,r]$ 从 $[1,10^{18}]$ 变成 $[x+1,x+10^{18}]$ 时,$\sum\limits_{i=l}^rf(i)$ 增加了 $x$ 。

设 $\sum\limits_{i=1}^{10^{18}}f(i)=q$ ,显然一组合法的 $[l,r]$ 为 $[a-q+1,a-q+10^{18}]$ 。

现在考虑怎么求出 $q$ 。通过打表可以发现 $\sum\limits_{i=1}^{10^x}f(i)=45x\cdot 10^{x-1}+1$ 。

那么 $q=81\times 10^{18}+1$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int _=1e18;

signed main() {
    int a=read(),q=(_%a*9%a*9%a+1)%a;
    printf("%lld %lld\n",a-q+1,a-q+_);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 33 PM