P1246 编码
solution
\(\quad\)先把位数比自己小的编码个数算出来，然后从左到右考虑位数和自己相等，但是比自己小的编码。这玩意和一般的字典序还不太一样，因为是升序，还要用组合数来计算。
code
#include<bits/stdc++.h>
using namespace std;
string s;
int ans, n;
int c(int m, int n) {
if (m == 0)return 1;
int a = 1;
for (int i = n; i > n - m; i--) a *= i;
for (int i = m; i > 1; i--) a /= i;
return a;
}
int main() {
cin >> s, n = s.size();
for (int i = 1; i < n; i++)
if (s[i] <= s[i - 1]) {
cout << 0;
return 0;
}
for (int i = 1; i < n; i++)ans += c(i, 26);
for (int i = 0; i < n; i++)
for (char j = (i == 0 ? 'a' : s[i - 1] + 1); j < s[i]; j++)
ans += c(n - i - 1, 'z' - j);
ans++;
cout << ans;
return 0;
}
P1069 [NOIP2009 普及组] 细胞分裂
solution
\(\quad\)能够满足条件的细胞的质因数一定包括 m1 的质因数，那么对 m1 先质因数分解，然后对于每一个细胞数都随便判断一下是否满足条件，然后统计一下答案就可以了。
code
#include <iostream>
using namespace std;
int n, m1, m2, s[10001], zs[10001] = {0}, mz, t = 2, c, ans = 0x7fffffff, l;
int main() {
cin >> n >> m1 >> m2;
for (int i = 1; i <= n; i++) cin >> s[i];
if (m1 == 1) {
cout << 0 << endl;
return 0;
}
while (m1 != 1) {
while (!(m1 % t)) m1 /= t, zs[t]++;
mz = max(mz, t);
zs[t++] *= m2;
}
for (int i = 1; i <= n; i++) {
l = 0;
for (int j = 2; j <= mz; j++) {
if (!zs[j]) continue;
c = 0;
while (!(s[i] % j)) s[i] /= j, c++;
if (!c) {
l = 0x7fffffff;
break;
}
l = max(l, (zs[j] - 1) / c);
}
ans = min(ans, l);
}
cout << (ans == 0x7fffffff ? -1 : ans + 1) << endl;
return 0;
}
P2638 安全系统
solution
\(\quad\)这个题目的题意很有误导性，每一个存储空间可以放任意数量的 0 和 1，而不是只能放一个。我一开始理解错了，然后就推了个错的组合数。不过知道了正确的题意后这个题目还是很简单。首先我们要知道 0 和 1 是两个独立的类别，所以我们分开考虑，0 放几个，1 放几个。确定了两个类别的数量后就发现其实就是要求：对于 n 个盒子，有几种放 x 个小球的方案数，那么这玩意就可以用插板法去做就可以了。一个不算技巧的技巧就是先预处理好杨辉三角。
code
#include<iostream>
using namespace std;
int n,a,b;
unsigned long long P[51][51],ans;
void Work(int n){
for(int i=0;i<=n;++i)P[i][0]=P[i][i]=1;
for(int i=2;i<=n;++i)
for(int j=1;j<=i;++j)
P[i][j]=P[i-1][j]+P[i-1][j-1];
}
int main()
{
cin>>n>>a>>b;
Work(n+max(a,b));
for(int i=0;i<=a;++i)
for(int j=0;j<=b;++j)
ans+=P[n+i-1][n-1]*P[n+j-1][n-1];
cout<<ans;
return 0;
}
P1835 素数密度
solution
\(\quad\)可以注意到区间长度其实是很短的，那么我们可以先预处理之前的一些质数，然后用线性筛的思想去筛，唯一要注意的就是 1 不是质数。
\(\quad\)其实我最开始的想法是对于每一个数用费马小定理去判断，复杂度大概是 \(O(nlogn)\) 不知道能不能过去。
code
略
P1072 [NOIP2009 提高组] Hankson 的趣味题
solution
\(\quad\)重点在于怎么控制这个范围。我们知道这个数字一定是 \(b_1\) 的因数，那么我们枚举 \(\sqrt b_1\) 的范围，然后判断是否满足条件即可。
code
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
int main() {
int T, ff;
cin >> T;
while (T--) {
int a0, a1, b0, b1, ans = 0;
cin >> a0 >> a1 >> b0 >> b1;
int b = sqrt(b1);
for (int i = 1; i <= b; i++) {
if (b1 % i == 0) {
if (i % a1 == 0 && gcd(i / a1, a0 / a1) == 1 && gcd(b1 / b0, b1 / i) == 1)
ans++;
int y = b1 / i;
if (i == y) continue;
if (y % a1 == 0 && gcd(y / a1, a0 / a1) == 1 && gcd(b1 / b0, b1 / y) == 1) ans++;
}
}
cout << ans << endl;
}
return 0;
}
P1403 [AHOI2005]约数研究
solution
\(\quad\)考虑每一个数的贡献，那么答案就是：
\[\sum_{i=1}^n \lfloor \frac{n}{i}\rfloor \]\(\quad\)这玩意可以用数论分块优化一下
code
int T,n,ans;
inline void solve(){
n=read();
for(int l=1,r=0;l<=n;l=r+1){
r=n/(n/l);
ans+=(n/l)*(r-l+1);
}
printf("%d",ans);
}
P3383 【模板】线性筛素数
solution
\(\quad\)略
code
#include <cstdio>
#include <cstring>
bool isPrime[100000010];
//isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
//Prime存质数
void GetPrime(int n)//筛到n
{
memset(isPrime, 1, sizeof(isPrime));
//以“每个数都是素数”为初始状态，逐个删去
isPrime[1] = 0;//1不是素数
for(int i = 2; i <= n; i++)
{
if(isPrime[i])//没筛掉
Prime[++cnt] = i; //i成为下一个素数
for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++)
{
//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
//当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
break; //重要步骤。见原理
}
}
}
int main()
{
int n, q;
scanf("%d %d", &n, &q);
GetPrime(n);
while (q--)
{
int k;
scanf("%d", &k);
printf("%d\n", Prime[k]);
}
return 0;
}
P1226 【模板】快速幂||取余运算
solution
\(\quad\)略
code
#include<iostream>
using namespace std;
long long b,p;
int k;
long long ksm(long long b,long long p,int k)
{
long long res=1;
if(p==0) return 1%k;
while(p!=0)
{
if(p%2==1) res*=b;
b*=b;
p/=2;
res%=k;
b%=k;
}
return res;
}
int main()
{
cin>>b>>p>>k;
cout<<b<<'^'<<p<<' '<<"mod"<<' '<<k<<'='<<ksm(b,p,k);
return 0;
}
P1075 [NOIP2012 普及组] 质因数分解
solution
\(\quad\)正常的想法就是以开根的范围去枚举，但事实如果你特别闲，打个 \(Pollard\space - \space rho\) 也是可以的。
code
#include<bits/stdc++.h>
#define ll long long
#define lll __int128
using namespace std;
ll max_factor, n;
inline ll gcd(ll a, ll b) {
return (b == 0) ? a : gcd(b, a % b);
}
inline ll ksm(ll x, ll p, ll mod) {
ll ans = 1;
while (p) {
if (p & 1) {
ans = (lll) ans * x % mod;
}
x = (lll) x * x % mod;
p >>= 1;
}
return ans;
}
inline bool mr(ll x, ll b) {
ll k = x - 1;
while (k)//如果能继续说明上次模数一定为1，那么下一次模数一定为正负1
{
ll cur = ksm(b, k, x);//b的k次方%x
if (cur != 1 && cur != x - 1) return 0;//不为1或x-1
if ((k & 1) == 1 || cur == x - 1) return 1;//k为奇数（无法继续）或 cur=x-1就认定是质数
k >>= 1;//开根，为下一次的平方，二次探测定理
}
return 1;
}
inline bool prime(ll x) {
if (x < 2 || x == 46856248255981ll) return 0;
if (x == 2 || x == 3 || x == 5 || x == 7 || x == 61 || x == 24251) return 1;
return mr(x, 2) && mr(x, 61);
}
inline ll f(ll x, ll c, ll n) {
return ((lll) x * x + c) % n;
}
inline ll pr(ll x) {
ll s = 0, t = 0, c = 1ll * rand() % (x - 1) + 1;
ll val = 1;
for (int i = 1;; i <<= 1, s = t, val = 1) {
for (int j = 1; j <= i; j++) {
t = f(t, c, x);
val = (lll) val * abs(t - s) % x;
if ((j % 127) == 0) {
ll d = gcd(val, x);
if (d > 1) return d;
}
}
ll d = gcd(val, x);
if (d > 1) return d;
}
}
inline void fac(ll x) {
if (x <= max_factor || x < 2) return;
if (prime(x)) {
max_factor = max_factor > x ? max_factor : x;
return;
}
ll p = x;
while (p >= x) p = pr(x);
while ((x % p) == 0) x /= p;
fac(x), fac(p);
}
int main() {
int T;
srand((unsigned) time(NULL));
ll n;
cin >> n;
max_factor = 0;
fac(n);
printf("%lld\n", max_factor);
return 0;
}
P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
solution
\[P=x\times x_0,Q=y\times x_0,gcd(x,y)=1 \] \[LCM=y_0=x\times y\times x_0 \] \[\frac{y_0}{x_0}=x\times y,gcd(x,y)=1 \]\(\quad\)那么对于上述式子求出有几对数字就可以了
code
int T,n,ans,x0,y;
inline void solve(){
x0=read();y=read();
if(y%x0) return puts("0"),void();
n=y/x0;
FOR(i,1,n){
if(n%i==0 && __gcd(i,n/i)==1) {++ans;}
}
printf("%d\n",ans);
}
P2926 [USACO08DEC]Patting Heads S
solution
\(\quad\)类似于线性筛的思想从小到大筛就可以了，因为数是两两不相同，可以证明复杂度是正确的。
code
#include<bits/stdc++.h>
using namespace std;
int a[10000005];
int n,mx=-100;
int b[10000005];
int cnt[10000005];
void get_factor(){
for (int i = 1; i <= 10000000; i++){
if(!b[i]) continue;
for (int j = 1; j <= 10000000 / i; j++){
if(b[i*j]) cnt[i*j]+=b[i];
if(i*j==i) cnt[i]--;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[a[i]]++;
}
get_factor();
for(int i=1;i<=n;i++)
cout<<cnt[a[i]]<<endl;
}
P3913 车的攻击
solution
\(\quad\)一个容斥 + 组合数学
code
#include <bits/stdc++.h>
#define ll long long
const int maxn=1e6+5;
using namespace std;
ll n,k;
ll x[maxn],y[maxn];
int main(){
scanf("%lld%lld",&n,&k);
for(ll i=0;i<k;i++){
//cin>>x[i]>>y[i];
scanf("%lld%lld",&x[i],&y[i]);
}
sort(x,x+k);
sort(y,y+k);
ll sizex=unique(x,x+k)-x;
ll sizey=unique(y,y+k)-y;
printf("%lld",n*n-(n-sizex)*(n-sizey));
return 0;
}
P1017 [NOIP2000 提高组] 进制转换
solution
\(\quad\)其实仿照正整数的求进制就可以了。就有一点要注意下：-15%-2=-1,-2*7-1=-15 ，但是我们需要让 15%-2=1,-2*8+1=-15，这种情况就需要特殊处理一下。
code
int T,n,base;
char zhb[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
inline void change(int n,int m){
if(!n) return ;
if(n>0) {change(n/m,m);cout<<zhb[n%m];}
else if(n%m==0) {change(n/m,m);cout<<0;}
else {change((n+1)/m+1,m);cout<<zhb[(n-((n+1)/m+1)*m)];}
}
P2789 直线交点数
solution
\(\quad\)我们不需要考虑每条直线具体在什么位置，而是需要考虑它们相对的平行与相交。假设已经确定了直线的个数，那么我们枚举平行的线段的个数，假设剩下的线段都不和这些线段平行，那么我们算出剩下的线段和平行的线段的交点数，再递归求解剩下的线段的交点数即可。
code
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
int n,MAX=-1,ans=0;
bool f[11000];
void g(int n,int k)
{
if (n==0) {f[k]=true;MAX=max(k,MAX);}
else for (int r=n;r>=1;r--)g(n-r,r*(n-r)+k);
}
int main()
{
cin>>n;
memset(f,false,sizeof(f));
g(n,0);
for (int i=0;i<=MAX;i++)
if (f[i]) ans++;
cout<<ans;
return 0;
}
P2822 [NOIP2016 提高组] 组合数问题
solution
\(\quad\)你可以把这个当作组合数意义下的递推，或者直接看作一个杨辉三角，不过这都无所谓，重要的就是预处理出所有的组合数，然后直接查询。
code
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,k) for(register int i=j;i<=k;i++)
#define rep(i,j,k) for(register int i=j;i>=k;i--)
#define lid id<<1
#define rid id<<1|1
#define db double
using namespace std;
int t,m,k,n;
ll f[2002][2002],flag[2002][2002];
void yh()
{
f[0][0]=f[1][0]=f[1][1]=1;
fo(i,2,2001)
{
f[i][0]=1;
fo(j,1,i)
{
f[i][j]=(f[i-1][j-1]%k+f[i-1][j]%k)%k;
flag[i][j]=flag[i-1][j]+flag[i][j-1]-flag[i-1][j-1];
if(f[i][j]==0) flag[i][j]++;
}
flag[i][i+1]=flag[i][i];
}
}
int main()
{
scanf("%d%d",&t,&k);
yh();
while(t--)
{
scanf("%d%d",&n,&m);
if(n<m) printf("%d\n",flag[n][n]);
else printf("%d\n",flag[n][m]);
}
return 0;
}
P1100 高低位交换
solution
\(\quad\)左/右边 16 位分别考虑一下就可以了
code
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n;
cin>>n;
int x=pow(2,15);
if(n>=x){
int a1=n>>16;
cout<<(((n-(a1<<16))<<16)+(a1))<<endl;
}else{
cout<<(n<<16)<<endl;
}
return 0;
}
P1866 编号
solution
\(\quad\)排序一下，然后就是基础的组合数学
code
#include<iostream>
#include<algorithm>
using namespace std;
int n,j,i,a[55];
long long t;
int main()
{
cin>>n;
t=1;j=0;
for(i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)
{
t=t*(a[i]-j);
t%=1000000007;
j++;
}
cout<<t<<endl;
return 0;
}
P1469 找筷子
solution
\(\quad\)可以以十进制作中转站去转
code
#include<iostream>
#include<cmath>
using namespace std;
int n, m, l, i, p, d, a[500];
long long h;
string s;
int main() {
cin >> n >> s >> m;
p = 0;
l = s.size();
h = 0;
if (n <= 10) {
for (i = 0; i < l; i++) {
h += pow(n, i) * (s[l - i - 1] - '0');
}
} else {
for (i = 0; i < l; i++) {
if (s[l - i - 1] >= 'A' && s[l - i - 1] <= 'Z') { h += pow(n, i) * (s[l - i - 1] - 'A' + 10); }
else { h += pow(n, i) * (s[l - i - 1] - '0'); }
}
}
while (h != 0) {
a[p] = h % m;
p++;
h = h / m;
}
for (d = p - 1; d >= 0; d--) {
if (a[d] < 10) cout << a[d];
else if (a[d] == 10) cout << 'A';
else if (a[d] == 11) cout << 'B';
else if (a[d] == 12) cout << 'C';
else if (a[d] == 13) cout << 'D';
else if (a[d] == 14) cout << 'E';
else if (a[d] == 15) cout << 'F';
}
return 0;
}
P1469 找筷子
solution
\(\quad\)全部异或一下落单的就是最后的答案
code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,ans;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
ans^=x;
}
cout<<ans;
return 0;
}