Bash Plays with Functions
题目背景：
thoj23
分析：
首先我们来搞一波打表找规律就会比较轻松的发现，f0 = 2k, 其中k表示n的不同的质因子的个数，所以我们也就可以发现f0 为积性函数，我们把稍微关注一下fr+1(n)的形式，就会发现
fr+1(n) = sigma(d|n)fr(d)
因为f0为积性函数，我们根据性质就可以知道fr+1也是一个积性函数，所以我们可以对于每一个询问，对n进行质因数分解，那么
n = p1e1p2e2...pqeq
由积性函数的性质，我们可以知道
fr(n) = fr(p1e1)* fr(p2e2)*...* fr(pqeq)
我们又再一次打表找一波规律就可以发现，其实pi为多少一点也不重要，所以我们完全可以通过递推的方式预处理出，在fi中自变量为任意一个质数的k次方的函数值，
cas[r][x] = sigma(0, x)cas[r- 1][i]
递推过程中用前缀和优化即可，然后针对询问分解质因数即可，所以最终的复杂度是O(nlogn)
注意：没什么好注意的（问我为什么打表找规律·····因为太弱了······）
Source：
#include #include #include #include #include #include #include using namespace std; inline char read() { static const int IN_LEN = 1024 * 1024; static char buf[IN_LEN], *s, *t; if (s == t) { t = (s = buf) + fread(buf, 1, IN_LEN, stdin); if (s == t) return -1; } return *s++; } template inline bool R(T &x) { static char c; static bool iosig; for (c = read(), iosig = false; !isdigit(c); c = read()) { if (c == -1) return false; if (c == '-') iosig = true; } for (x = 0; isdigit(c); c = read()) x = (x << 3) + (x << 1) + (c ^ '0'); if (iosig) x = -x; return true; } const int OUT_LEN = 1024 * 1024; char obuf[OUT_LEN], *oh = obuf; inline void writechar(char c) { if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf; *oh++ = c; } template inline void W(T x) { static int buf[30], cnt; if (!x) writechar(48); else { if (x < 0) writechar('-'), x = -x; for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48; while (cnt) writechar(buf[cnt--]); } } inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); } const int MAXN = 1e6 + 10; const int mod = 1e9 + 7; int cnt; int prime[MAXN]; int cas[21][MAXN]; bool bo[MAXN]; inline int add(int x, int t) { x += t; if (x > mod) x -= mod; return x; } inline void pre(int n) { bo[1] = true; for (int i = 2; i <= n; ++i) { if (!bo[i]) prime[++cnt] = i; for (int j = 1; j <= cnt && prime[j] * i <= n; ++j) { bo[i * prime[j]] = true; if (i % prime[j] == 0) break; } } for (int i = 0; i <= n; ++i) cas[1][i] = i + 2; for (int i = 2; i <= 19; ++i) for (int j = 0; j <= n; ++j) if (j) cas[i][j] = add(cas[i - 1][j], cas[i][j - 1]); else cas[i][j] = cas[i - 1][j]; } inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } inline void get(int x, int n, int ct) { long long ans = 1, cnt; for (int i = 1; i <= ct; ++i) { if (!bo[x]) { ans = (ans * (n + 2)) % mod; break; } cnt = 0; for (cnt = 0; x % prime[i] == 0; x /= prime[i], cnt++); if (cnt) ans = (ans * 1LL * cas[cnt][n]) % mod; if (x == 1) break; } W(ans), writechar('\n'); } int q, x, n; int main() { // freopen("in.in", "r", stdin); pre(1000000); R(q); while (q--) { R(n), R(x); get(x, n, cnt); } flush(); return 0; }