我们称 "简要题意" 给出的三个要求分别为 "条件 1","条件 2","条件 3".
条件 3 长得比较丑, 考虑转化一下. 把不等式两边同时开 \(ij\)次根, 得到:\(\sqrt[i]{x_i}<\sqrt[j]{x_j+1}\). 这样左边只和 \(i\)有关, 右边只和 \(j\)有关. 于是条件 3 就转化为了 \((\max_{i=1}^{n}\sqrt[i]{x_i})<(\min_{i=1}^{n}\sqrt[i]{x_i+1})\).
根据转化后的条件 3, 加上条件 1(\(x_1=2\)), 我们可以推出:\(2^i\leq x_i<3^i\).
再考虑条件 2. 我们发现: 如果条件 2 不成立, 则条件 3 和条件 1 不可能同时成立. 证明:
首先, 如果存在一对 \(i<j\), 且 \(x_i>x_j\). 则 \(x_j+1\leq x_i\), 即 \(\sqrt[j]{x_j+1}<\sqrt[i]{x_i}\), 不满足我们转化后的条件 3.
再考虑如果序列非严格递增, 即存在 \(x_i=x_{i+1}\). 设 \(x_i=a\), 若条件 3 成立, 则 \(a^{i+1}<(a+1)^i\). 两边同时除以 \(a^i\)得 \(a<\left(\frac{a+1}{a}\right)^i\). 若条件 1 成立, 则 \(a\geq 2^i\). 即 \(\left(\frac{a+1}{a}\right)^i>2^i\),\(\frac{a+1}{a}>2\),\(a<1\). 与 \(2^i\leq a<3^i\)矛盾. 故不可能在条件 2 不成立时, 让条件 1 和条件 3 同时成立.
所以, 当条件 1 和条件 3 同时成立时, 条件 2 也一定成立. 于是我们接下来可以不考虑条件 2.
因为对每个 \(x_i\),\(2^i\leq x_i<3^i\), 我们考虑每个 \(x_i\)的所有可能的取值, 把所有取值对应的 \(\sqrt[i]{x_i}\)和 \(\sqrt[i]{x_i+1}\)都求出来. 将所有可能的 \(\sqrt[i]{x_i}\)和 \(\sqrt[i]{x_i+1}\)的值放在一起, 排序并去重.
我们称排序去重后, 相邻的两个值之间的区间为一段小区间. 可以发现: 所有小区间和所有合法序列一一对应. 即: 小区间的数量就是本题的答案! 证明:
考虑一个合法的序列的 \([(\max_{i=1}^{n}\sqrt[i]{x_i}),(\min_{i=1}^{n}\sqrt[i]{x_i+1})]\)这个区间.
如果我们选择一段小区间 \([l,r]\)作为这个 \([\max,\min]\)的区间. 对每个位置 \(i\), 考虑它的所有可能的 \(x_i\)的值, 一定存在唯一的一个值 \(a(2^i\leq a<3^i)\), 使得 \(\sqrt[i]{a}\leq l\)且 \(\sqrt[i]{a+1}\geq r\). 我们令 \(x_i=a\). 这样, 我们就构造出了一个合法的序列. 即对于每段小区间, 我们都能构造出一个合法的序列.
考虑如果 \(x_i<a\), 则会使得 \(\sqrt[i]{x_i+1}<r\); 如果 \(x_i>a\), 则会使得 \(\sqrt[i]{x_i}>l\), 这都不符合要求. 因此, 每段小区间 \([l,r]\)只会唯一对应一个合法的序列(就是我们构造出的那个).
考虑如果某个序列的 \([\max,\min]\)这个区间不是一段小区间, 即它中间跨过了至少一个点. 假设这个点属于 \(x_j\). 则 \(x_j\)就无法找到一个取值, 使得 \(\sqrt[j]{x_j}\leq l\)且 \(\sqrt[j]{x_j+1}\geq r\). 因此, 不存在某个合法序列的 \([\max,\min]\)不是一段小区间. 所以: 每个合法序列, 都唯一对应一段小区间.
问题转化为如何求出小区间的数量.
依次考虑所有 \(i\in[2,n]\). 设 \(f(i)\)表示 \(i\)这个位置会新增多少点. 则
\[ f(i)=3^i-2^i-\sum_{d|i,d<i}f(d) \]
移项得:
\[ \sum_{d|i}f(d)=3^i-2^i \]
设 \(g(i)=3^i-2^i\), 则 \(g(i)=\sum_{d|i}f(d)\). 根据莫比乌斯反演, 有:
\[ f(i)=\sum_{d|i}\mu(\frac{i}{d})g(d) \]
我们要求的是:
\[ \begin{align} ans=&\sum_{i=1}^{n}f(i)\=&\sum_{i=1}^{n}\sum_{d|i}\mu(\frac{i}{d})g(d)\=&\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i) \end{align} \]
用数论分块 + 杜教筛 (记忆化), 可以在 \(O(n^\frac{2}{3})\) 时间内求出 \(ans\).
参考代码:
- //problem:nflsoj553
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define mk make_pair
- #define lob lower_bound
- #define upb upper_bound
- #define fst first
- #define scd second
- typedef unsigned int uint;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int,int> pii;
- /* ------ by:duyi ------ */ // dysyn1314
- const int MAXN=1e7;
- ll n;int MOD,PHIMOD,INV2;
- inline int mod1(int x){return x<MOD?x:x-MOD;}
- inline int mod2(int x){return x<0?x+MOD:x;}
- inline void add(int &x,int y){x=mod1(x+y);}
- inline void sub(int &x,int y){x=mod2(x-y);}
- inline int pow_mod(int x,int i){int y=1;while(i){if(i&1)y=(ll)y*x%MOD;x=(ll)x*x%MOD;i>>=1;}return y;}
- int p[MAXN/10],cnt,mu[MAXN+5];
- bool v[MAXN+5];
- void sieve(){
- mu[1]=1;
- for(int i=2;i<=MAXN;++i){
- if(!v[i])p[++cnt]=i,mu[i]=-1;
- for(int j=1;j<=cnt&&(ll)i*p[j]<=MAXN;++j){
- v[i*p[j]]=1;
- if(i%p[j]==0)break;
- mu[i*p[j]]=-mu[i];
- }
- }
- //cerr<<cnt<<endl;
- for(int i=1;i<=MAXN;++i)mu[i]+=mu[i-1],mu[i]=mod2(mu[i]);
- }
- map<ll,int>mp;
- int summu(ll n){
- if(n<=MAXN)return mu[n];
- if(mp.count(n))return mp[n];
- int res=1;
- for(ll i=2,j;i<=n;i=j+1){
- j=n/(n/i);
- sub(res,(ll)(j-i+1)*summu(n/i)%MOD);
- }
- return mp[n]=res;
- }
- int sumg(ll n){
- if(!n)return 0;
- return mod2((ll)mod2(pow_mod(3,(n+1)%PHIMOD)-3)*INV2%MOD-mod2(pow_mod(2,(n+1)%PHIMOD)-2));
- }
- int main() {
- cin>>n>>MOD;PHIMOD=MOD-1;INV2=pow_mod(2,MOD-2);
- sieve();
- int ans=0;
- for(ll i=1,j;i<=n;i=j+1){
- j=n/(n/i);
- add(ans,(ll)mod2(sumg(j)-sumg(i-1))*summu(n/i)%MOD);
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3438577.html