题解：CF2043D Problem about GCD

bsdsdb · 2024-12-27 18:36:33 · 题解

题意：给定 l,r,g，求 x,y 满足（或报告不存在）：

令 l'\gets\left\lceil\dfrac{l}{g}\right\rceil,r'\gets\left\lfloor\dfrac{r}{g}\right\rfloor，则问题就变为了求 [l',r'] 内的差最大互质对。l'=r' 无解，否则至少有解 (l',l'+1)，可以枚举：

// python
for leng in range(r - l, 0, -1):
    for x in range(l, r - leng + 1):
        y = x + leng
        if math.gcd(x, y) == 1:
            print(leng)
            sys.exit(0)

如果能证明 \forall l<r\le 10^{18}:\exist x,y:x\in[l,l+k_1],y\in[r-k_2,r]:\gcd(x,y)=1 的话，枚举量就是 \mathcal O((k_1+k_2)^2)，总复杂度就是 \mathcal O((k_1+k_2)^2\log r)。接下来我们证明 k_1=5,k_2=16 是合法的。

证：他们模 $6$ 的余数肯定是 $0,1,2,3,4,5$。如果余 $1$ 的那个是 $5$ 的倍数，那么余 $5$ 的那个就不是 $5$ 的倍数；如果余 $5$ 的那个是 $5$ 的倍数，那么余 $1$ 的那个就不是 $5$ 的倍数。
记这个数为 a，他的所有质因数记作一个单调递增的序列 \{p_m\}，那么 m\le12,p_1 到 p_m 分别大于等于 7,11,13,\cdots,47。

证：7\times11\times13\times17\times19\times23\times29\times31\times37\times41\times43\times47\times53=1\ 086\ 305\ 282\ 573\ 001\ 491>10^{18}。
记 $f(x)$ 为连续 $17$ 个数可能的最多的 $x$ 的倍数的数量，也就是 $f(x):=\left\lceil\frac{17}{x}\right\rceil$，则：

\begin{aligned} \sum_{i=1}^mf(p_i)\le\ &f(7)+f(11)+\cdots+f(47)\\\ &=3+2+2+1+1+1+1+1+1+1+1+1\\ &=16 \end{aligned}

也就是说，连续 17 个数里最多有 16 个数是 p_i 的倍数，还有一个不是任何 p_i 的倍数，也就是和 [l,l+5] 中的某个数互质。

~~其实理论上还可以用模拟退火做，但是我只卡到了第 10 个数据点~~

#include <bits/stdc++.h>
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>T;
using namespace std;
using namespace chrono;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef double ldb;
//#define umap unordered_map
#define umap __gnu_pbds::cc_hash_table
#define mkp make_pair
#define prque priority_queue
#define emp emplace
#define empb emplace_back
#define empf emplace_front
random_device rndv;
// #define LOCAL
mt19937_64 rd(ll(11451491918102023));
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const vector<ll> millerrabin = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
const double eps = 1e-8;
inline void enter(){putchar('\n');}
inline void space(){putchar(' ');}
inline ll readll(){ll ret=0,k=1;char c;do{c=getchar();if(c=='-'){k=-1;}}while(('0'>c)|('9'<c));do{ret=(ret<<3)+(ret<<1)+c-48;c=getchar();}while(('0'<=c)&(c<='9'));return ret*k;}
inline void read(ll&x){x=readll();}
inline char readchar(){char ret;do{ret=getchar();}while(ret<=32);return ret;}
inline void read(char&x){x=readchar();}
inline string readstr(){string ret;char c;do{c=getchar();}while(c<=32);do{ret+=c;c=getchar();}while((c>32)&(c!=EOF));return ret;}
inline void read(string&x){x=readstr();}
inline void write(ll x){if(!x){putchar('0');return;}if(x<0){putchar('-');x*=-1;}char op[20]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){putchar(op[cur--]);}}
inline ostream& operator<<(ostream& out, __int128 x){if(!x){out<<"0";return out;}if(x<0){out<<"-";x*=-1;}char op[40]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){out<<op[cur--];}return out;}
// -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

const ll rdpyl = 3;

ll l, r, g, _T;
/* used in simulate annealing
chrono::high_resolution_clock::time_point st;

inline pll f(ll x, ll y) {
    if (__gcd(x, y) == 1) {
        return mkp(abs(x - y), -min(x, y));
    } else {
        return mkp(0, 0);
    }
}

inline ldb rdr() {
    return ldb(1) * rd() / ((__int128(1) << 64) - 1);
}
inline ll rnd(ll x, ll y) {
    x = min(x, r);
    if (x == y) {
        return x;
    }
    ll nr = rd() % (y - x) + x;
    if (nr < l) {
        return min(l + ll((rd() % 18) / 10), r);
    }
    if (nr > r) {
        return max(r - ll(rd() % rdpyl), l);
    }
    return nr;
}
*/

int mian(ll t) {
    read(l), read(r), read(g);
    if ((l + g - 1) / g * g > r) {
        puts("-1 -1");
        return 0;
    }
    l = (l + g - 1) / g, r = r / g;
    if (l == 1 && r == 1) {
        write(g), space(), write(g), enter();
        return 0;
    }
    if (l >= r) {
        puts("-1 -1");
        return 0;
    }
    for (ll len = r - l + 1; len >= 1; --len) {
        for (ll x = l; x + len - 1 <= r; ++x) {
            ll y = x + len - 1;
            if (__gcd(x, y) == 1) {
                write(x * g), space(), write(y * g), enter();
                return 0;
            }
        }
    }
    /* simulate annealing method:
    ll ansx, ansy, curx, cury;
    ll initpyl = 30;
    if (r - l <= initpyl) {
        ansx = curx = l, ansy = cury = r;
    } else {
        ansx = curx = l + (initpyl >> 1), ansy = cury = r - (initpyl >> 1);
    }
    pll fa = f(ansx, ansy), fc = f(curx, cury);
    for (ldb _T = initpyl; _T >= 0.9; _T *= 0.95) {
        ll T = _T;
        ll x = rnd(curx - T, curx + (T >> 1));
        ll y;
        if (fa.first) {
            y = rnd(x + fa.first, cury + T);
        } else {
            y = rnd(cury - T, cury + T);
        }
        if (y < x) {
            swap(x, y);
        }
        pll ff = f(x, y);
        if (ff > fa) {
            ansx = x, ansy = y, fa = ff;
        }
        if ((ff > fc) || (rdr() < exp(ldb(-1) * abs(ff.first - fc.first) / T))) {
            curx = x, cury = y, fc = ff;
        }
    }
    ll rdfy = 15;
    while (duration_cast<microseconds>(high_resolution_clock().now() - st).count() < t * 950) {
        ll x = rnd(ansx - rdfy, ansx + (rdfy >> 1));
        ll y;
        if (fa.first) {
            y = rnd(x + fa.first, ansy + rdfy);
        } else {
            rnd(ansy - rdfy, ansy + rdfy);
        }
        if (y < x) {
            swap(x, y);
        }
        pll ff = f(x, y);
        if (ff > fa) {
            ansx = x, ansy = y, fa = ff;
        }
    }
    if (ansx > l && __gcd(ansx - 1, ansy - 1) == 1) {
        --ansx, --ansy;
        if (ansx > l && __gcd(ansx - 1, ansy - 1) == 1) {
            --ansx, --ansy;
        }
    }

    write(ansx * g), space(), write(ansy * g), enter();
    */
    return 0;
}
int main() {
//  st = high_resolution_clock().now();
    ll T;
    read(T);
    _T = T;
    while (T--) {
        rd = mt19937_64(345675342698ll);
        mian(_T - T);
    }
    return 0;
}

;             ;;;;;;;;;;;         ;
;                      ;         ; ;
;                    ;          ;   ;
;                   ;          ;     ;
;                 ;           ;;;;;;;;;
;               ;            ;         ;
;              ;            ;           ;
;;;;;;;;;;;   ;;;;;;;;;;   ;             ;

   ;                        ;
  ;                          ;
 ;                            ;
;                              ;
;                              ;
;                              ;
 ;                            ;
  ;         ;;          ;;   ;
   ;        ;;          ;;  ;