JZOJ 6455 小 D 的交通

什么年代了还有人出高精题啊……

首先题目相当于构造一个正整数序列，将其中不互质的点连边后能连通。

考虑令序列首位为所有小于 N 的质数乘积，则根据更相减损术，除了第二个位置显然都能与首位连边。
然后我们发现并不是很好解决。

考虑令序列中心为所有小于等于 N2 的质数乘积，则除了相邻的两个位置显然都能与中心连边。
可以牺牲两个质数的贡献来使这两个点连通。
但是牺牲了这两个质数之后又会有点不连通，于是再用几个大于 N2 的质数使它们连通即可。

然后用 CRT 合并即可。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
const long long ANS[] = {2184,27829,27828,87890,87890,171054,171054,323510,127374,323510,151062,151062,151062,151061,151060,151059,151058,672540170262,672540170262,2101641443862,2101641443862,4152621523031};
int n,m;
int vis[N + 5],cnt,prime[N + 5];
int a[6],pos,l,r,mid;
struct bigint
{
    static const int LEN = 10000;
    static const int w = 1e9;
    int a[LEN],len;
    inline void clear()
    {
        memset(a,0,sizeof a),len = 0;
    }
    inline bigint(int x = 0)
    {
        clear();
        for(a[len++] = x % w,x /= w;x;a[len++] = x % w,x /= w);
    }
    inline int operator%(const int &mod)
    {
        int ret = 0;
        for(register int i = len - 1;~i;--i)
            ret = ((long long)ret * w % mod + a[i] % mod) % mod;
        return ret;
    }
    inline int &operator[](const int &x)
    {
        return a[x];
    }
    inline const int &operator[](const int &x) const
    {
        return a[x];
    }
    inline bigint &operator+=(const bigint &o)
    {
        len = max(len,o.len);
        int k = 0;
        for(register int i = 0;i < len;++i)
            a[i] = a[i] + o[i] + k,k = a[i] / w,a[i] %= w;
        for(;k;a[len++] = k % w,k /= w);
        return *this;
    }
    inline bigint &operator-=(const bigint &o)
    {
        for(register int i = 0;i < len;++i)
            a[i] -= o[i],a[i] < 0 && (a[i] += w,--a[i + 1]);
        for(;!a[len - 1] && len > 1;--len);
        return *this;
    }
    inline bigint operator*(const bigint &o)
    {
        bigint ret;
        ret.len = len + o.len - 1;
        __int128 k = 0;
        for(register int i = 0;i < ret.len;ret[i] = k % w,k /= w,++i)
            for(register int j = 0;j <= i;++j)
                a[j] && o[i - j] && (k += (long long)a[j] * o[i - j],1);
        for(;k;ret[ret.len++] = k % w,k /= w);
        return ret;
    }
    inline bigint &operator*=(const bigint &o)
    {
        *this = *this * o;
        return *this;
    }
    inline bool operator<(const bigint &o) const
    {
        if(len ^ o.len)
            return len < o.len;
        for(register int i = len - 1;~i;--i)
            if(a[i] ^ o[i])
                return a[i] < o[i];
        return 0;
    }
    inline bool operator>=(const bigint &o) const
    {
        return !(*this < o);
    }
    void print()
    {
        printf("%d",a[len - 1]);
        for(register int i = len - 2;~i;--i)
            printf("%09d",a[i]);
    }
} ans,mod = 1;
int fpow(int a,int b,int mod)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
void crt(int a,int p)
{
    int w = (long long)(a - ans % p + p) * fpow(mod % p,p - 2,p) % p;
    ans += mod * w,mod *= p;
    for(;ans >= mod;ans -= mod);
}
bigint mul(int l,int r)
{
    if(l == r)
        return prime[l];
    int mid = l + r >> 1;
    return mul(l,mid) * mul(mid + 1,r);
}
int main()
{
    freopen("teleports.in", "r", stdin),freopen("teleports.out", "w", stdout); 
    scanf("%d", &n);
    if(n == 1)
    {
        puts("1");
        return 0;
    }
    if(n <= 16)
    {
        puts("No solution");
        return 0;
    }
    if(n <= 38)
    {
        printf("%lld\n",ANS[n - 17]);
        return 0;
    }
    for(register int i = 2;i <= n;++i)
    {
        if(!vis[i])
            prime[++cnt] = i;
        for(register int j = 1;j <= cnt && i * prime[j] <= n;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
        }
    }
    l = 1,r = cnt;
    while(l <= r)
        mid = l + r >> 1,
        2 * prime[mid] < n ? (pos = mid,l = mid + 1) : (r = mid - 1);
    mod = mul(1,pos - 2);
    a[0] = prime[pos - 1],a[1] = prime[pos];
    2 * prime[pos + 1] == n && (mod *= prime[++pos],1);
    a[2] = prime[pos + 1],a[3] = prime[pos + 2],a[4] = prime[pos + 3],a[5] = prime[pos + 4];
    crt(1,a[0]),crt(a[1] - 1,a[1]),crt(a[0],a[2]),crt(a[3] - a[0],a[3]),crt(a[1],a[4]),crt(a[5] - a[1],a[5]);
    ans < (n + 1) / 2 && (ans += mod,1),(ans -= (n - 1) / 2).print();
}