首页 > 代码库 > BZOJ1300 [LLH邀请赛]大数计算器
BZOJ1300 [LLH邀请赛]大数计算器
一开始以为暴力搞，后来看了数据范围还以为要FFT，各种被虐，然后Orz Seter大神！！！
我只想到了前三位：a * b <=> 10^(log(a) + log(b))，于是把乘的数都先log了最后再变回去就可以了。。。
然后后九位的方法：
Seter："对于素数a，在N!中出现了N / a + N / a ^ 2＋...次"
于是C(M, N) = N! / M! / (N - M)!就可以求每个质因数出现的次数，搞定！
1 /************************************************************** 2 Problem: 1300 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:164 ms 7 Memory:1792 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 14 using namespace std;15 typedef long long LL;16 17 int n, m;18 LL ans = 1;19 bool p[1000001];20 21 int main(){22 scanf("%d%d", &n, &m);23 m = min(m, n - m);24 25 int i, j, x, y, c, s;26 double k = 0, f = 1;27 for (i = 2; i <= n; ++i)28 if (!p[i]){29 for (j = n, x = n - m, y = m; j;){30 c = (j /= i) - (x /= i) - (y /= i), s = i;31 for (c <<= 1; c >>= 1; s *= s)32 if (c & 1) ans *= s, ans %= (LL) 1e12;33 }34 if (i <= 1000)35 for (j = i * i; j <= n; j += i)36 p[j] = 1;37 }38 for (i = 1; i <= m; ++i){39 if (f > 1e7)40 k += log10(f), f = 1;41 f = f * (n - m + i) / i;42 }43 k += log10(f);44 45 if (k < 13) printf("%lld\n", ans);46 else printf("%d...%09lld\n", (int) (pow(10, k - floor(k) + 2) + 1e-5), ans % (int) 1e9);47 return 0;48 }
p.s.话说Seter竟然可以C、C++混用，真是碉堡了。。。
BZOJ1300 [LLH邀请赛]大数计算器
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。