## 【BZOJ 4725】[POI2017] Reprezentacje ró?nicowe

### 解题报告

$63$项之后的，我们可以推公式推出来答案是多少

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;

int n,tot,vis[N],L[N],R[N],que[N];
LL f[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void insert(int w) {
for (int i=w-1;i;i--) {
if (abs(f[w]-f[i]) >= N) break;
vis[abs(f[w]-f[i])] = 1;
}
}

inline int query() {
for (int i=1;i;i++)
if (!vis[i]) return i;
}

inline void Get_Ans(int w, int id) {
for (int j=2;j;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] == w) {
L[id] = i; R[id] = j;
return;
}
}
}
}

inline void query(int w) {
for (int j=2;j;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] == w) {
cout<<j<<' '<<i<<endl;
return;
}
}
}
}

int main() {
f[1] = 1; f[2] = 2; vis[1] = 1;
for (int i=3;i<=120;i++) {
if (i&1) f[i] = f[i-1] << 1;
else f[i] = f[i-1] + query();
insert(i);
}
for (int j=2;j<=63;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] > 1e9) continue;
que[++tot] = f[j] - f[i];
}
}
que[++tot] = (1e9) + 10;
sort(que+1, que+1+tot);
for (int i=1;i<tot;i++) Get_Ans(que[i], i);
p = lower_bound(que+1, que+1+tot, x) - que;
if (que[p] == x) printf("%d %d\n",R[p], L[p]);
else if (x <= 90) query(x);
else printf("%lld %lld\n",(x-90-p+62)*2ll+120,(x-90-p+62)*2ll+119);
}
return 0;
}


## 【Codeforces 757E】Bash Plays with Functions

### 解题报告

Ⅰ. 设$x$的素因子种类数为$g(x)$那么$f_0(x)$等于$2^{g(x)}$
Ⅱ. 由规律Ⅰ可得，$f_0(x)$为积性函数，又$f_i(x)=f_{i-1} * 1(x)$，于是我们可用归纳证明得$f_i(x)$均为积性函数
Ⅲ. 设$p$为素数，$f_r(p^k)$与$p$无关，且满足递推式：$f_r(p^k)=\sum\limits_{i=0}^{k}{f_{r-1}(p^i)}$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000009;
const int MOD = 1000000007;

int tot,vis[N],pri[N],sur[N],g[N][21];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void prework() {
for (int i=2;i<N;i++) {
if (!vis[i]) pri[++tot] = i, sur[i] = i;
for (int j=1;j<=tot&&i*pri[j]<N;j++) {
vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
g[0][0] = 1;
for (int i=1;i<=20;i++) g[0][i] = 2;
for (int i=1;i<N;i++) {
for (int j=0;j<=20;j++) {
g[i][j] = ((j? g[i][j-1]: 0) + g[i-1][j]) % MOD;
}
}
}

inline int solve(int a, int b) {
int ret = 1;
for (int cnt=0,p=sur[b];b>1;cnt=0,p=sur[b]) {
while (b % p == 0) b /= p, cnt++;
ret = (LL)ret * g[a][cnt] % MOD;
}
return ret;
}

int main() {
prework();
printf("%d\n",solve(a,b));
}
return 0;
}


## 【BZOJ 1053】[HAOI2007] 反素数ant

### 题解

1.质因数是连续的，也就是说我们只用考虑37及之前的质因数
2.较大的质因数个数一定少于较小的质因数的个数

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int SZ = 12;

int n,num,vout,pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37};

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int DFS(int t, int last, int w, int v) {
if (t == 13) {
if (v == num) {
vout = min(vout, w);
} else if (v > num) {
vout = w;
num = v;
}
} else {
for (int i=0,cur=1;i<=last;i++,cur*=pri[t]) {
if ((LL)cur * w > n) break;
else {
DFS(t+1, i, w*cur, v*(i+1));
}
}
}
}

int main(){
puts("1");
} else {
DFS(1,30,1,1);
printf("%d\n",vout);
}
return 0;
}


## 【BZOJ 4513】[SDOI2016] 储能表

—– UPD 2016.9.29 —–

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL f[62][2][2][2],g[62][2][2][2],n,m,MOD,k;

int main(){
int T; cin>>T; while (T--) {
cin>>n>>m>>k>>MOD;
memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
g[61][0][0][0] = 1;
for (int i=60;~i;i--) {
int t1 = (n>>i)&1, t2 = (m>>i)&1, t3 = (k>>i)&1;
for (int a=0;a<2;a++) for (int b=0;b<2;b++) for (int c=0;c<2;c++) if (g[i+1][a][b]) {
for (int x=0,w,wa,wb,wc;x<2;x++) for (int y=0;y<2;y++) {
if (w=x^y, (!a&&x>t1) || (!b&&y>t2) || (!c&&w<t3)) continue;
wa = (a||x<t1); wb = (b||y<t2); wc = (c||w>t3);
(g[i][wa][wb][wc] += g[i+1][a][b]) %= MOD;
(f[i][wa][wb][wc] += ((f[i+1][a][b] + (((w-t3)*((1LL<<i)%MOD))%MOD)*g[i+1][a][b]%MOD)%MOD + MOD) % MOD) %= MOD;
}
}
}
cout<<f[0][1][1][1]<<endl;
}
return 0;
}