S+数论，高斯消元，线性基
A. B进制数与B-1倍数查询问题
我们可以通过十进制下 $\text{mod } 9$ 的结论，猜想：在 $b$ 进制下的数 $x$：$x \equiv S(x) (\text{mod } b-1)$，其中 $S(x)$ 表示 $x$ 在 $b$ 进制下所有数位总和。
接下来我们证明，设 $x$ 在 $b$ 进制下有唯一拆分：$x=x_p\times b^p+x_{p-1}\times b^{p-1}+…+x_1\times b+x_0$，且 $p=\lceil \log_{10} x\rceil $，且$ \forall 0\le i \le p \to 0\le x_i \le b-1$
则 $\forall 0\le i \le p$ ，可以发现，$ (b-1) | (b^i-1) $ .
所以，我们可以得到：
$$
\begin{aligned}
x &=x_p\times b^p+x_{p-1}\times b^{p-1}+…+x_1\times b+x_0 \\
&=(b^p-1)x_p+(b^{p-1}-1)x_{p-1}+…+(b-1)x_1+x_p+x_{p-1}+…+x_1+x_0
\end{aligned}
$$
又因为，$ (b-1) | [(b^p-1)x_p+(b^{p-1}-1)x_{p-1}+…+(b-1)x_1] $；
所以得到：
$$
x \equiv x_p+x_{p-1}+…+x_1+x_0 (\text{mod } b-1)
$$
剩下的很简单了，因为题目中给出了 $a_i \ge 1$ ，所以直接将 $S(x) \text{mod } (b-1)$ 这个数的数字减一，二分查找答案即可。
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
intc N=1e6+10;
int b,q,sum,a[N];
signed main() {
Cios;
cin>>b>>q;
for (int i=0;i<b;i++) {
cin>>a[i];
sum+=a[i]*i;
}
if (sum
for (int i=1;i<b;i++) a[i]+=a[i-1];
while (q--) {
int k;
cin>>k;
if (k>=a[b-1]) cout<<-1<<endl;
else cout<<upper_bound(a,a+b,k)-a<<endl;
}
return 0;
}B. 放入糖果
考虑构建抽屉。抽屉为 $0,1,2,⋯,n−1$，一共 $n$个抽屉。
根据抽屉原理，前 $n+1$ 次肯定会出现重复的抽屉被选中，并且当重复时，将形成一个周期，所以可以得出时间复杂度 $O(\text{min}(n,k))$ 。
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
intc N=1e6+10;
int n,k,a[N],dfn[N],sums[N];
signed main() {
Cios;
cin>>n>>k;
for (int i=0;i<n;i++) cin>>a[i];
int flag=1,nw=0,lst=0,sum=0;
while (k>0) {
//cout<<sum<<endl;
if (flag&dfn[nw]) {
flag=0;
int sumk=sums[dfn[lst]]-sums[dfn[nw]-1];
sumk*=k/(dfn[lst]-dfn[nw]+1);
sum+=sumk;
k
if (k<=0) break;
// for (int i=0;i<n;i++) cout<<dfn[i]<<" ";
}
dfn[nw]=dfn[lst]+1;
sum+=a[nw];
sums[dfn[nw]]=sums[dfn[lst]]+a[nw];
lst=nw;
nw=sum
k--;
}
cout<<sum<<endl;
return 0;
}E. 密码箱
根据题目，我们可以很容易得出，我们要求一个数 $x\in \mathbb N$ 且 $x \le n$，使得 $x^2 \equiv 1 (\text{mod } n)$。
所以我们可以设 $x^2 = nk+1 $，其中 $k\in \mathbb N$
之后得出：
$$
\begin{aligned}
x^2 &= nk+1 \\
x^2-1 &= nk \\
(x+1)(x-1) &=nk \\
\end{aligned}
$$
所以我们得到：$n | (x+1)(x-1)$。
之后，找到 $a\in \mathbb N , b\in \mathbb N$，使得 $ab=n$ 且 $a|(n+1) \land b|(n-1)$ 或 $a|(n-1) \land b|(n-1)$。
所以我们只要在 $0\le a \le \lfloor \sqrt{n} \rfloor$ 范围内枚举 $a$ 即可。
注意，无解时，当且仅当 $n=1$。
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n;
vector<int> x;
signed main() {
Cios;
cin>>n;
if (n==1) {
cout<<"None"<<endl;
return 0;
}
cout<<"1\n";
for (int i=1;i*i<=n;i++) {
if (n
int a=i,b=n/a;
for (int j=b+1;j<=n;j+=b) {
if ((j+1)
}
for (int j=b-1;j<=n;j+=b) {
if ((j-1)
}
}
}
sort(x.begin(),x.end());
int nn=unique(x.begin(),x.end())-x.begin()-1;
for (int i=0;i<=nn;i++) cout<<x[i]<<endl;
return 0;
}
评论（0）
暂无评论