正題

題目鏈接:http://www.ybtoj.com.cn/problem/912

---

題目大意

給出$L,R$，求有多少長度在$[L,R]$之間的字符串滿足依次取出所有偶數位置的放在最前面后，與原字符串相同。字符集是所有小寫字母。

$1\le Q\le 5,1\le L\le R\le 10^{10},R?L\le 5\times 10^4$

---

解題思路

這個東西可以理解為給出一些相等關系的邊，然后求聯通塊的數量$G$，然后方案就是$26^G$。

設$G(x)$表示$x$的聯通塊數量。首先奇偶數不一樣很麻煩，發現如果對于奇數$x$有$G(x)=G(x?1)+1$（最后一個自己連自己）。所以我們只需要考慮偶數的。

$n$為偶數時給出的條件其實就是$S_i=S_{2i\%(n+1)}$，然后此時考慮點$x$，有$d=gcd(x,n+1)$，那么有$x=dk$。我們讓$x$向$2x\%(n+1)$連邊，考慮求出$x$所在環的環長，也就是求一個最小的$r$滿足$x\times 2^r\equiv x(modn+1)$，就是滿足$2^r\equiv 1(mod\frac{n+1}{gcd(x,n+1)})$，后文記做$ord(\frac{n+1}{gcd(x,n+1)})$。然后滿足$gcd(x,n+1)=d$的都在一些大小為$r$的環中相互連接，這樣的$x$有$\phi (\frac{n+1}{gcd(x,n+1)})$個。所以這樣的環有$\frac{\phi (\frac{n+1}{gcd(x,n+1)})}{ord(\frac{n+1}{gcd(x,n+1)})}$，然后改成枚舉$\frac{n+1}{gcd(x,n+1)}$就有一個比較舒服的式子
$$G(n)=\sum _{d|n,d>1}\frac{\phi (d)}{ord(d)}$$

上面那個$\phi$很好求，考慮怎么求下面那個$ord$。
和原根類似的使用試除法，首先根據歐拉定理肯定有$ord(n)|\phi (n)$。然后考慮對于$\phi (n)$的每個約數$x$如果滿足$2^{\frac{w}{x}}\equiv 1(modn)$就代表可以除去這個$x$。

但是這樣每次來搞還是很慢，這里還有一個挺顯然的結論
$$gcd(x,y)=1?ord(x\times y)=lcm(ord(x),ord(y))$$
證明的話首先定理$a=lcm(x,y)$，再設一個$2^b\equiv 1(modxy)$，那么有$2^{b?a}\equiv 1(modxy)$，然后這樣更相減損下去最后就有$2^{gcd(a,b)}\equiv 1(modxy)$，所以如果$b<a$那么有，然后因為$a=lcm(x,y)$也就是這個就是新的最小的$gcd$。

所以我們就只需要求出所有需要的$ord(p^k)$就好了。

然后我們可以先枚舉$\sqrt{R}$以內的質數然后來給所有$[L,R]$中的數質因數分解，然后對于里面的每個$x$用搜索來求所有的約數。

---

code

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<cctype> #define ll __int128 using namespace std; const ll N=1e5+10,P=1e9+7; ll q,L,R,ans,tot,cnt,G; ll pri[N],phi[N],mk[N][35],p[35],c[35]; bool v[N];vector<ll >cp[N]; map<ll,map<ll,ll> >mp; ll read() {ll x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } void print(ll x){if (x>9) print(x/10); putchar(x%10+48); return; } ll power(ll x,ll b,ll P){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } ll ord(ll p,ll k){if(p<N&&mk[p][k])return mk[p][k];if(p>pri[cnt]&&mp[p][k])return mp[p][k];ll m=power(p,k,1e18),x,w=p-1;x=m/p*(p-1); while(x%p==0){ll z=power(2,x/p,m);if(z!=1)break;x/=p;}if(w>=L&&w<=R+2){ll wz=w-L;for(ll wc=0;wc<cp[wz].size();wc++){ll i=cp[wz][wc];while(x%pri[i]==0){ll z=power(2,x/pri[i],m);if(z!=1)break;x/=pri[i];}while(w%pri[i]==0)w/=pri[i];} }else{for(ll i=1;pri[i]*pri[i]<=w&&i<=cnt;i++){if(w%pri[i])continue;while(x%pri[i]==0){ll z=power(2,x/pri[i],m);if(z!=1)break;x/=pri[i];}while(w%pri[i]==0)w/=pri[i];}}if(w>1){if(x%w==0){ll z=power(2,x/w,m);if(z==1)x/=w;}}if(p<N)mk[p][k]=x;else mp[p][k]=x;return x; } void prime(){phi[1]=1;for(ll i=2;i<N;i++){if(!v[i])pri[++cnt]=i;for(ll j=1;j<=cnt&&i*pri[j]<N;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;}}return; } ll lcm(ll x,ll y){ll d=__gcd(x,y);return x*y/d; } void dfs(ll x,ll ph,ll od){if(x>tot){G+=ph/od;return;}dfs(x+1,ph,od);for(ll i=1,w=p[x];i<=c[x];i++)dfs(x+1,ph*(w/p[x]*(p[x]-1)),lcm(od,ord(p[x],i))),w=w*p[x];return; } ll work(ll n){tot=0;ll wz=n-L;for(ll w=0;w<cp[wz].size();w++){ll i=cp[wz][w];p[++tot]=pri[i];c[tot]=0;while(n%pri[i]==0)c[tot]++,n/=pri[i];}if(n>1)p[++tot]=n,c[tot]=1;G=-1;dfs(1,1,1);return G; } signed main() { // freopen("language.in","r",stdin); // freopen("language.out","w",stdout); // scanf("%lld",&q);q=read();prime();while(q--){ // scanf("%lld%lld",&L,&R);L=read();R=read();ans=0;for(ll i=0;i<=R-L+2;i++)cp[i].clear();for(ll i=1;i<=cnt;i++){ll x=pri[i],l=L/x,r=(R+2)/x;for(ll j=l;j<=r;j++){if(j*x<L||j*x>R+2)continue;cp[j*x-L].push_back(i);}}for(ll i=L/2;i<=R/2;i++){ll tmp=work(i*2ll+1);if(i*2ll>=L)ans=(ans+power(26,tmp,P))%P;if(i*2ll+1<=R)ans=(ans+power(26,tmp+1,P))%P;}print(ans);putchar('\n'); // printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的YbtOJ#912-神秘语言【结论,欧拉定理】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。