首页 > 代码库 > Codeforces Round #232 (Div. 1)
Codeforces Round #232 (Div. 1)
这次运气比较好，做出两题。本来是冲着第3题可以cdq分治做的，却没想出来，明天再想好了。
A. On Number of Decompositions into Multipliers
题意：n个数a1，a2, a3...an求n个数相乘与a1*a2*a3*a4...an相等的排列个数。
分析：首先应该对ai分解质因数，求出所有ai中质因数及个数，枚举排列中每个数包含的质因数个数，例如质因数qi，有ni个，相应的排列中数包含质因数qi个数设为x1，x2,....xn, x1+x2+x3..+xn = ni , 那么对于qi共有C(ni+n-1, n-1)种情况。简单来说就是将ni分成n部分，这样想：有ni个球，需要分成n部分，也就是在n个球中插入n-1根木棍，这样分成n部分就相当于ni+n-1中选n-1个位置。最后把所有质因子可能的划分情况相乘起来就行了。
注意：分解质因数最后一个质因数可能很大！
代码：
1 #include <bits/stdc++.h> 2 #define in freopen("solve_in.txt", "r", stdin); 3 #define bug(x) printf("Line %d : >>>>>>>\n", (x)); 4 #define pb push_back 5 6 using namespace std; 7 typedef long long LL; 8 typedef map<int, int> Mps; 9 const int M = (int)1e9+7;10 const int maxn = 555;11 const int maxm = (int)1e5 + 100;12 LL inv[maxn];13 int a[maxn];14 Mps Div;15 vector<int> dv;16 17 LL powmod(LL a, LL b) {18 LL res = 1;19 while(b) {20 if(b&1)21 res = (res*a)%M;22 b >>= 1;23 a = (a*a)%M;24 }25 return res;26 }27 void getInv(int n) {28 for(int i = 1; i < n; i++) {29 inv[i] = powmod(i, M-2);30 }31 }32 void getDiv(int x) {33 int m = (int)sqrt(x+.5);34 for(int i = 2; i <= m; i++) {35 if(x%i == 0) {36 if(Div[i] == 0)37 dv.pb(i);38 while(x%i == 0) {39 Div[i]++;40 x/=i;41 }42 }43 }44 if(x > 1) {45 if(Div[x] == 0)46 dv.pb(x);47 Div[x]++;48 }49 }50 LL nCr(LL n, LL m) {51 LL res = 1;52 for(int i = 0; i < m; i++) {53 res = res*(n-i)%M*inv[i+1]%M;54 if(res < 0)55 res += M;56 }57 return (res + M)%M;58 }59 int main() {60 61 getInv(maxn);62 int n;63 scanf("%d", &n);64 for(int i = 1; i <= n; i++) {65 scanf("%d", a+i);66 getDiv(a[i]);67 }68 LL ans = 1;69 for(int i = 0; i < (int)dv.size(); i++) {70 int x = dv[i];71 ans = ans*nCr(Div[x]+n-1, n-1)%M;72 }73 cout<<ans<<endl;74 return 0;75 }
B. On Sum of Fractions
题意：给定n， u(i)表示不超过i的最大质数， v(i)表示大于i的最小质数。求对于所有的2<= i <= n , sum{1/(u(i)*v(i)}， 最简分式结果。
分析：
列出n的前几个数的1/u(i)*v(i)，发现对于两个相邻素数pi, pi+1间的数i， 1/u(i)*v(i)结果是一样的。也就是说 对于 pi <= x < pi+1， sum{1/u(x)v(x)},化简后就是， 1/u(x)-1/v(x), 得到这个结论后，每次找到大于n的一个素数pi+1，结果就变成两部分， x < pi, 和 pi <= x < n， 第一部分化简就是1/2-1/pi ,第二部分：n-pi+1/(pi*pi+1), 两者之和合并一下就会得到一个表达式：2*(n+1)-2*(pi+pi+1)-pi*pi+1/(2*pi*pi+1)。求质数，用Miller-Rabin法判断前后两个质数就可以了。
代码：
1 #include <bits/stdc++.h> 2 #define in freopen("solve_in.txt", "r", stdin); 3 #define bug(x) printf("Line %d : >>>>>>>\n", (x)); 4 #define pb push_back 5 6 using namespace std; 7 typedef pair<int, int> PII; 8 typedef long long LL; 9 typedef map<int, int> Mps;10 11 LL powmod(LL a, LL b, LL c) {12 LL res = 1;13 while(b) {14 if(b&1) res = res*a%c;15 b >>= 1;16 a = (a*a)%c;17 }18 return res;19 }20 bool test(int n, int a, int d) {21 if(n == 2)return true;22 if(n == a) return true;23 if((n&1) == 0) return false;24 while(!(d&1)) d >>= 1;25 int t = powmod(a, d, n);26 while((d != n-1) && (t != 1) && (t != n-1)) {27 t = (LL)t*t%n;28 d <<= 1;29 }30 return (t == n-1) || (d&1) == 1;31 32 }33 bool isPrime(int n) {34 if(n < 2) return false;35 int a[] = {2, 3, 61};36 for(int i = 0; i <= 2; i++) if(!test(n, a[i], n-1)) return false;37 return true;38 }39 pair<LL, LL> getPrime(LL n) {40 LL x = n;41 x++;42 PII ans;43 while(1) {44 if(isPrime(x)) {45 ans.first = x;46 break;47 }48 x++;49 }50 x = n;51 while(1) {52 if(isPrime(x)) {53 ans.second = x;54 break;55 }56 x--;57 }58 return ans;59 }60 LL getGcd(LL a, LL b) {61 return !b ? a : getGcd(b, a%b);62 }63 int main() {64 65 int T;66 int n;67 for(int t = scanf("%d", &T); t <= T; t++) {68 scanf("%d", &n);69 if(n == 2) {70 puts("1/6");71 } else {72 PII u = getPrime(n);73 LL x = u.first, y = u.second;74 LL a = 2*(n+1)-2*(x+y)+x*y;75 LL b = 2*x*y;76 LL c = getGcd(a, b);77 printf("%I64d/%I64d\n", a/c, b/c);78 }79 }80 return 0;81 }
C. On Changing Tree
题意：
Codeforces Round #232 (Div. 1)