数论，高斯消元，线性基

S+数论，高斯消元，线性基 A. B进制数与B-1倍数查询问题 需要的前置知识：设一个 B 进制数为 x，数位和为 f(x)，那么： x \equiv f(x) (\bmod B-1) 证明： \begin{align} 设x&=\sum_{i=0}^{n}a_i·B^i \\ \because x&=\sum_{i=0}^{n}a_i+a_i·(B^i-1) \\ \therefore x&=\sum_{i=0}^{n}a_i+a_i·(B-1)·(\sum_{j=0}^{i-1}a^{j}) \\ & 又 a_i·(B-1)·(\sum_{j=0}^{i-1}a^{j}) \equiv 0 & \\ & \therefore x \equiv \sum_{i=0}^{n}a_i & \end{align} 由此得证。 根据这一点，为了使这个数足够大，首先肯定要更多的数位， 所以我们减去一个 sum\bmod (b-1)， 最后在前缀和数组中二分查找 k 即可。 代码： #include using namespace std; #define int long long const int N=1e6+5; int b,q,k,s; int a[N]; signed main(){ cin>>b>>q; for(int i=0;i>a[i],s+=a[i]*i; if(s%(b-1)) a[s%(b-1)]--; for(int i=1;i>k,k++; int ans=lower_bound(a,a+b,k)-a; if(ans==b) cout `#include using namespace std; #define int long long const int N=1e6+5; int b,q,k,s; int a[N]; signed main(){ cin>>b>>q; for(int i=0;i>a[i],s+=a[i]*i; if(s%(b-1)) a[s%(b-1)]--; for(int i=1;ia[i]+=a[i-1]; while(q--){ cin>>k,k++; int ans=lower_bound(a,a+b,k)-a; if(ans==b) cout"-1\n"; else cout } return 0; }` C++ B. 放入糖果 这题先模拟，直到找到了一个周期，就可以直接统计答案。 代码还是比较好写的： #include using namespace std; #define int long long const int N=2e5+5; int n,k,t; int a[N],s[N],tag[N]; signed main(){ memset(tag,-1,sizeof tag); cin>>n>>k; for(int i=0;i>a[i]; for(int i=1;i `#include using namespace std; #define int long long const int N=2e5+5; int n,k,t; int a[N],s[N],tag[N]; signed main(){ memset(tag,-1,sizeof tag); cin>>n>>k; for(int i=0;i>a[i]; for(int i=1;i s[i]=s[i-1]+a[s[i-1]%n]; if(tag[s[i-1]%n]!=-1){ t=i-1; break; } tag[s[i-1]%n]=i; } if(t==0) couts[k]; else{ int q=tag[s[t]%n]; couts[q-1]+(s[t]-s[q-1])*((k-q+1)/(t-q+1))+(s[q-1+(k-q+1)%(t-q+1)]-s[q-1]); } return 0; }` C++ D. 充实 这道题需要证明一个结论： 若存在一条从根节点到叶子节点的路径使点权的最大公倍数是 2 的幂，答案就加一， 可惜我不会证明。 代码如下： #include using namespace std; const int N=1e5+5; int T,n,f,ans; int a[N]; vector t[N]; void dfs(int u,int x){ if(!t[u].size()) ans+=!(x&x-1); else for(int v:t[u]) dfs(v,__gcd(x,a[v]-a[u])); } main(){ cin>>T; while(T--){ cin>>n,ans=0; for(int i=0;i>f,t[f].push_back(i); for(int i=1;i>a[i]; dfs(1,0); cout `#include using namespace std; const int N=1e5+5; int T,n,f,ans; int a[N]; vectorint> t[N]; void dfs(int u,int x){ if(!t[u].size()) ans+=!(x&x-1); else for(int v:t[u]) dfs(v,__gcd(x,a[v]-a[u])); } main(){ cin>>T; while(T--){ cin>>n,ans=0; for(int i=0;it[i].clear(); for(int i=2;i>f,t[f].push_back(i); for(int i=1;i>a[i]; dfs(1,0); cout } return 0; }` C++ E. 密码箱 题意可以简化为找到一个数 x 满足： \begin{align} x^2 &\equiv 1 (\bmod n), x\in[0,n) \\ \therefore x^2-1 &\equiv 0 \\ (x+1)(x-1) &\equiv 0 \\ \therefore (x+1)(x-1)&=n·k \end{align} 设有 a,b 满足 a·b=n \land a|(x-1) \land b|(x+1) 枚举因数即可。 代码： #include using namespace std; #define int long long int n,idx; int ans[10000005]; signed main(){ cin>>n; for(int i=1;i*i=0) ans[++idx]=j-1; for(int j=0;j `#include using namespace std; #define int long long int n,idx; int ans[10000005]; signed main(){ cin>>n; for(int i=1;i*iif(n%i==0){ int a=i,b=n/i; for(int j=0;jif((j-2)%a==0&&j-1>=0) ans[++idx]=j-1; for(int j=0;jif((j+2)%a==0&&j+1ans[++idx]=j+1; } sort(ans+1,ans+1+idx); idx=unique(ans+1,ans+1+idx)-ans-1; for(int i=1;ians[i] return 0; }` C++ F. 余数之和 \begin{align} &\sum_{i=1}^{n}k \bmod i \\ =&\sum_{i=1}^{n}k-i·\lfloor \frac{k}{i} \rfloor \\ =&n·k-\sum_{i=1}^{n} \sum_{j=1}^{k} i·(\lfloor \frac{j}{i} \rfloor - \lfloor \frac{j-1}{i} \rfloor) \\ =&n·k-\sum_{j=1}^{k} \sum_{i=1}^{n} i·[i|j] \\ =&n·k-\sum_{j=1}^{k} \sigma (j) \end{align} 对于正因数和的前缀和， 分块计算每一段贡献为 \lfloor \frac{k}{i} \rfloor 的区间的总贡献即可。 代码： #include using namespace std; #define int long long int n,k; signed main(){ cin>>n>>k; int l=1,ans=n*k; n=min(n,k); while(l `#include using namespace std; #define int long long int n,k; signed main(){ cin>>n>>k; int l=1,ans=n*k; n=min(n,k); while(l int t=k/l,r=(t==0?n:min(k/t,n)); ans-=(l+r)*(r-l+1)/2*t; l=r+1; } cout return 0; }` C++ J. 线性基1 线性基模板，代码： #include using namespace std; #define int long long const int N=1e5+5; int n; struct basis{ int p[100]; void insert(int a){ for(int i=50;i>=0;i--) if((a>>i)&1){ if(!p[i]){ p[i]=a; break; } a^=p[i]; } } int check(){ int ans=0; for(int i=63;i>=0;i--) ans=max(ans,ans^p[i]); return ans; } }b; main(){ cin>>n; while(n--){ int x; cin>>x; b.insert(x); } cout `#include using namespace std; #define int long long const int N=1e5+5; int n; struct basis{ int p[100]; void insert(int a){ for(int i=50;i>=0;i--) if((a>>i)&1){ if(!p[i]){ p[i]=a; break; } a^=p[i]; } } int check(){ int ans=0; for(int i=63;i>=0;i--) ans=max(ans,ans^p[i]); return ans; } }b; main(){ cin>>n; while(n--){ int x; cin>>x; b.insert(x); } coutb.check(); return 0; }` C++