CF468C

Aryper · 2021-09-23 21:40:35 · 个人记录

Hack it!

非常思维的一道构造题。

考验了乱搞的能力。。。

我们发现这个 a 相比于 l 和 r 的最大值非常小，然后就有了乱搞的启发。

比如说，我们取 l=0，r=10^{100}-1，虽然这样并不可以取，但是我们可以让它们都加上 x。然后神奇的事情就发生了，我们假设那个求和的函数为 g(l,r)，那么就会有 g(l+x,r+x)=g(l,r)+x。

原因就是，我们同时加的时候较低位的数字被抵消了，只有最高位的数字做出了贡献。然而此时的最高位就是 1，那么加上了 x 个 1，就让 g(l,r) 多了 x。

然后就是直接乱搞了。

因为这里的 a 顶在 long long 的线上，所以为了偷懒，直接使用 __int128，再开个 C++17 解决。

时间复杂度 O(1)。

更为神奇的方法是直接把极限调在 10^{18} 上，然后代码就会变得非常短，手算的东西就多一些。然后 p=(81\cdot lim) \bmod a，l=a-p，r=lim+a-p-1。

但是同样为了防止溢出，我们的一般运算是通过两次乘 9 来实现的。

代码：

#include<iostream>
#include<cstdio>
#define ll __int128
using namespace std;

ll a,b,p,l,sum,ans,pos;

ll aa[105];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    a=read();

    b=10;p=101;ans=1;

    while(p>0) {
        if(p&1) ans=(ans*b)%a;
        b=(b*b)%a;p>>=1;
    }

    for(ll i=1;i<=9;i++) {
        sum=(sum+ans*i%a)%a;
    }

    l=a-sum;

    write(l);putchar(' ');
    aa[1]=1;l--;pos=101;
    while(l>0) {
        aa[pos--]=l%10;l/=10;
    }
    for(ll i=1;i<=101;i++) {
        write(aa[i]);
    }

    return 0;
}

代码：（10^{18}）

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll lim=1e18;

ll a,l,r;

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    a=read();

    l=a-lim%a*9%a*9%a;

    r=lim-1+l;

    write(l);putchar(' ');write(r);

    return 0;
}