首页 > 代码库 > BZOJ2721 [Violet 5]樱花
BZOJ2721 [Violet 5]樱花
先令n! = a：
1 / x + 1 / y = 1 / a => x = y * a / (y - a)
再令 k = y - a：
于是x = a + a ^ 2 / k => k | a ^ 2
故等价于求a ^２的约数个数
素数筛一下什么的就好了嘛
1 /************************************************************** 2 Problem: 2721 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:588 ms 7 Memory:2408 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 12 using namespace std;13 typedef long long ll;14 const int N = 1000005;15 const int Cnt = 80005;16 const int mod = 1000000007;17 18 int n;19 bool F[N];20 int cnt, p[Cnt], c[Cnt];21 ll ans = 1;22 23 int main() {24 int i, j, t;25 scanf("%d\n", &n);26 for (i = 2; i < N; ++i) {27 if (!F[i]) p[++cnt] = i;28 for (j = 1; j <= cnt && p[j] * i < N; ++j) {29 F[p[j] * i] = 1;30 if (p[j] % i == 0) break;31 }32 }33 for (i = 1; i <= cnt; ++i)34 for (j = p[i]; j <= n; j += p[i])35 for (t = j; t % p[i] == 0; t /= p[i]) ++c[i];36 for (i = 1; i <= cnt; ++i)37 (ans *= (c[i] << 1 | 1)) %= mod;38 printf("%lld\n", ans);39 return 0;40 }
BZOJ2721 [Violet 5]樱花
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。