https://www.51nod.com/Challenge/Problem.html#problemId=1586
一眼看过去居然一点思路都没有的,一言不合就打表,打贡献表。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n = 25;
int a[200];
void update_b(int id) {
for(int i = 1; i <= id; ++i) {
if(id % i == 0) {
a[i]++;
}
}
}
void show_c(int id) {
memset(a, 0, sizeof(a));
for(int i = 1; i <= id; ++i) {
if(id % i == 0) {
update_b(i);
}
}
printf("c[%d]=
", id);
for(int i = 1; i <= n; ++i) {
printf("%d%c", a[i], "
"[i == n]);
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
for(int i = 1; i <= n; ++i) {
show_c(i);
}
return 0;
}
好像a[i]位置对c[j]的贡献就是d(j/i)的样子,所以就预处理出d表就完事了?
数字不大,d表有nlogn的出法。但是暴力分解因子果断T,预处理所有数的因子也是T。原因在于因子是根号级别的,但是正解是直接更新a的倍数,是log级别的。
考虑a本身,它对应的另一个因子是1,2a对应的因子是2……这样可以用一个循环直接更新。期望复杂度是O(nlogn)的,而分解质因子暴力的期望复杂度则是O(n*n^{3/4})。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
int d[MAXN + 5], a[MAXN + 5];
int p[MAXN + 5], ptop;
bool np[MAXN + 5];
void sieve(int n = MAXN) {
np[1] = d[1] = 1;
for(int i = 2; i <= n; ++i) {
if(!np[i])
p[++ptop] = i, d[i] = 2, a[i] = 1;
for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
np[t] = 1;
if(i % p[j])
d[t] = d[i] * d[p[j]], a[t] = 1;
else {
d[t] = d[i] / (a[i] + 1) * (a[i] + 2);
a[t] = a[i] + 1;
break;
}
}
}
}
const int BufferSize = 1 << 16;
char buffer[BufferSize], *head, *tail;
inline char Getchar() {
if(head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (head = buffer) + l;
}
return *head++;
}
inline int read() {
int x = 0;
char c = Getchar();
for(; c < '0' || c > '9'; c = Getchar())
;
for(; c >= '0' && c <= '9'; c = Getchar())
x = (x << 3) + (x << 1) + c - '0';
return x ;
}
inline void _write(ll x) {
if(x > 9)
_write(x / 10);
putchar(x % 10 + '0');
}
inline void write(ll x) {
_write(x);
putchar('
');
}
ll c[MAXN + 5] = {};
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
sieve();
int n = read(), q = read();
for(int i = 1; i <= q; ++i) {
int op = read();
if(op == 1) {
int x = read();
int y = read();
for(int j = x, k = 1; j <= n; j += x, ++k)
c[j] += (ll)d[k] * y;
} else {
int x = read();
write(c[x]);
}
}
return 0;
}
文件快读是真的快啊。