為什么這幾天想要寫博客呢？
因為感覺自己也沒有幾天了，現在多寫一些至少證明自己涉足過OI這個領域
# 題面
若記 \(a,b\) 的「NIM積」為 \(a\odot b\)，則有以下性質：
- 對于任意正整數 \(k\)，數集 \(A_k=\{x\mid x\in\mathbb{N},x<2^{2^k}\}\) 滿足 \(\forall x,y\in A_k,x\odot y\in A_k\)（運算在 \(A_k\) 內封閉）；
- \(a\odot 1=a\)（單位元）；
- \(a\odot 0=0\)（零元）；
- \(a\odot b=b\odot a\)（交換律）；
- \((a\odot b)\odot c=a\odot(b\odot c)\)（結合律）；
- \(a\odot(b\otimes c)=(a\odot b)\otimes(b\odot c)\)，其中 \(\otimes\) 是按位異或（分配律）；
記 \(a^{\odot b}=\overbrace{a\odot a\odot a\odot\cdots\odot a}^{b個}\)，給定 \(a,b\) 求解方程：
\[a^{\odot x}=b \]多組詢問，每次給定 \(a,b\)，資料規模：\(a,b< 2^{64}\)，資料組數不超過 \(100\)，
# 決議
不是很清楚「NIM積」的一些技巧，所以此篇不涉及「NIM積」計算的優化，
另外本篇中極有可能有不嚴謹的地方 ╯︿╰ 希望各位能指出
記數集 \(A=\{x\mid x\in[1,2^{64}),x\in\mathbb{N}^+\}\)，（注意排除了 \(0\)）
根據NIM積的上述性質，可以推斷 \((A,\odot)\) 是乘法群（滿足封閉性、結合律、有單位元和逆元），以下簡記「NIM積」為「乘法」，
群的大小（數集的大小為）記為 \(F=2^{64}-1\)，則有 \(\forall a\in A,a^F=1\)（可以類比整數模 \(n\) 乘法群），
回過頭來看題目給定的問題
\[a^x=b \]是一個離散對數的經典模型，但是數集大小 \(F\) 太大，并不能 \(O(\sqrt F)\) 用 BSGS 暴力求解，
觀察到 \(F\) 并非素數，實際上質因數分解得到
\[F=3\times5\times17\times257\times641\times65537\times6700417 \]這些質因子都不大，考慮能否對單個質因子求解，然后得到原問題的答案，
比如對質因子 \(p\) 單獨求解，不妨設 \(x=kp+r\)，則：
\[a^{kp+r}=b \]經過下列推導（注意 \(p\mid F\)）：
\[\begin{aligned} a^{kpF+rF}&=b^F\\ a^{kF+r\frac{F}{p}}&=b^{\frac{F}{p}}\\ \end{aligned} \]上述方程有兩個未知數 \(k,r\)，但是因為 \(a^F=1\)，有
\[\Big(a^{\frac{F}{p}}\Big)^{r}=b^{\frac{F}{p}} \]類似的，定義 \(a\) 的階 \({\rm ord}\ a\) 為滿足 \(a^k=1\) 的最小正整數 \(k\)，則
- \({\rm ord}\ a\mid F\)，顯然有 \({\rm ord}\ a\le F\)；
- 若 \(k\mid F\)，則 \({\rm ord}\ a^k=\frac{{\rm ord}\ a}{k}\)，
因此 \({\rm ord}\ a^{\frac{F}{p}}=\frac{p}{F}{\rm ord}\ a\le p\)，也就是說，如果 \(\Big(a^{\frac{F}{p}}\Big)^{r}=b^{\frac{F}{p}}\) 的解 \(r\) 存在，那么必然存在特解 \(r=r_0\)，\(r_0\le p\)，
\(p\) 較小，可以直接 BSGS \(O(\sqrt{p})\) 的復雜度內求解，
解出 \(r\) 后，有：
\[\begin{aligned} a^{kp+r}&=b\\ (a^p)^k&=b\cdot a^{-r} \end{aligned} \]\(a^{-r}=a^{F-r}\)，類似于費馬小定理求逆元，于是轉化為子問題，\(a'=a^p\)，\(b'=b\cdot a^{-r}\)，求解未知數 \(k\)，
記對第 \(i\) 個質因子執行上述程序后得到的方程是
\[a_i^{k_i}=b_i \]其中 \(k_i\) 是未知數，于是有 \(a_i=a_{i-1}^{p_i},b_i=b_{i-1}\cdot a^{-r_i}\)，\(k_i=k_{i+1}p_{i+1}+r_{i+1}\)，
對每個質因子都做一次上述程序后，最后我們會得到一個關于 \(k_7\) 的方程 \(a_7^{k_7}=b_7\)，這個方程如何求解？
實際上這個方程不需要求解——\(a_7=a^{p_1p_2\cdots p_7}=a^F=1\)，此時若 \(b_7=1\)，則有無窮解，取樸素解 \(k_7=1\)；若 \(b_7\neq1\)，則無解，
然后 \(k_i=k_{i+1}p_{i+1}+r_{i+1}\) 往回代，代出 \(k_1\)，然后得到 \(x=k_1p_1+r_1\)，
# 源代碼
/*Lucky_Glass*/
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long llong;
typedef unsigned long long ullong;
#define con(type) const type &
template<class T>inline T rin(T &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
template<class T>inline void wri(con(T)r){
if(r<10) putchar(char('0'+r));
else wri(r/10),putchar(char('0'+r%10));
}
const int PRES[]={3,5,17,257,641,65537,6700417};
const int SQRPRES[]={2,3,5,17,26,257,2589};
const ullong CONF=18446744073709551615ull;
int ncas;
ullong varr[10];
int nontag[10];
// 摘自 Freopen 的博客 https://blog.csdn.net/qq_35950004/article/details/107669351
ullong nim[256][256];
ullong nimMul(ullong a,ullong b,ullong L=64){ // L
if(a <= 1 || b <= 1) return a * b;
if(a < 256 && b < 256 && nim[a][b]) return nim[a][b];
/*
X = 2 ^ L , L = 2 ^ p
([a / X]X + a%X) * ([b / X]X + b%X)
c = a % X , d = b % X
*/
ullong S = (1ull << L) - 1;
if(a <= S && b <= S) return nimMul(a,b,L>>1);
ullong A = nimMul(a>>L,b>>L,L>>1) , B = nimMul((a>>L)^(a&S),(b>>L)^(b&S),L>>1) , C = nimMul(a&S,b&S,L>>1);
S++;
ullong r = nimMul(A,S>>1,L>>1) ^ (S * (C^B)) ^ C;
if(a < 256 && b < 256) nim[a][b] = r;
return r;
}
ullong nimPow(ullong a,ullong b){
ullong r=1;
while(b){
if(b&1) r=nimMul(a,r);
a=nimMul(a,a),b>>=1;
}
return r;
}
int solve(con(ullong)a,con(ullong)b,con(int)conp,con(int)consqr){
ullong x=nimPow(a,CONF/conp),y=nimPow(b,CONF/conp);
map<ullong,int> mem;
ullong tmp=y;
for(int i=0;i<=consqr;i++,tmp=nimMul(tmp,x))
if(!mem.count(tmp))
mem[tmp]=i;
tmp=1;
ullong tmp_per=nimPow(x,consqr);
for(int i=0;i<=consqr;i++,tmp=nimMul(tmp,tmp_per))
if(mem.count(tmp) && i*consqr>=mem[tmp])
return i*consqr-mem[tmp];
return -1;
}
int main(){
// freopen("input.in","r",stdin);
rin(ncas);
while(ncas--){
ullong a,b;
rin(a),rin(b);
bool fai=false;
memset(nontag,false,sizeof nontag);
for(int i=0;i<7;i++){
int res=solve(a,b,PRES[i],SQRPRES[i]);
if(res==-2){
nontag[i]=true;
continue;
}
if(res==-1){
fai=true;
break;
}
varr[i]=res;
ullong _b=nimMul(b,nimPow(a,CONF-res)),_a=nimPow(a,PRES[i]);
a=_a,b=_b;
}
if(a!=b || nimMul(a,a)!=b) fai=true;
if(fai) printf("-1\n");
else{
ullong x=0,mod=1;
for(int i=6;~i;i--){
if(nontag[i]) continue;
mod*=PRES[i];
x=x*PRES[i]+varr[i];
if(x<0) x+=mod;
}
wri(x),putchar('\n');
}
}
return 0;
}
THE END
Thanks for reading!
若我是宇宙里渺小的一顆星星
在你目光里找到方向 從未想過 如此幸運
或許我曾片刻 指引迷途的你
勇敢前行 別在意
——《守望者》By 司南
> Link 守望者-網易云
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263247.html
標籤：其他
上一篇：那些你不知道的DOU+投放技巧，以及常見的審核失敗原因丨國仁網路
下一篇：圖示加代碼 搞懂線性表（一）