Split Divisibilities (Project Euler 598)

题目大意：

求将$100!$ 拆成$a*b$的方案数,其中$a<=b$并且它们的约数个数一样多。

思路：

先将$100!$质因数分解, 结果如图：

首先想到一个暴力DP, dp[i][j][k]表示考虑完前i个质数, 目前a有j个约数,b有k个约数的方案数。用map保存状态。

答案就是sum(dp[25][j][j]).

但是状态数会很多(大概有1e8个状态),所以考虑中途相遇法。对前3个质数做一次DP, 然后对后面22个质数做一次DP。

最后答案就是 sum (dp1[3][i1][j1] * dp2[22][i2][j2]) 条件是 i1 * i2 = j1 * j2. 即 i1 / j1 = j2 / i2 .

一个优化是只保存 j和k互质的状态。然后最后答案的时候枚举 i1,j1, 在 dp2中查找 j2 / i2 = i1 / j1的点。

因为a<=b,所以最后答案还需要除以2.

代码：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <set>

 #include <cstring>

 #include <map>

 #include <queue>

 using namespace std;

 typedef long long ll;

 #define N 10000000

 #define M 1100

 typedef pair<int,int> pii;

 bool flag[N];

 int p[N],phi[N];

 struct node

 {

     ll x,y;

     bool operator < (const node &t)const

     {

         return y*t.x<x*t.y;

     }

     node (ll _x = , ll _y = ){x = _x; y = _y;}

 };

 map<node, ll> mp;

 ll Gcd(ll x, ll y)

 {

     ll tmp;

     while (y)

     {

         tmp = x % y;

         x = y, y = tmp;

     }

     return x;

 }

 void Get_Primes(int lim)

 {

     phi[]=;

     for (int i=;i<=lim;i++)

     {

         if (!flag[i]) p[++p[]]=i,phi[i]=i-;

         for (int j=;j<=p[] && i*p[j]<=lim;j++)

         {

             flag[i*p[j]]=true;

             if (i%p[j]==)

             {

                 phi[i*p[j]]=phi[i]*p[j];

                 break;

             }

             else phi[i*p[j]]=phi[i]*(p[j]-);

         }

     }

 }

 map<pair<ll,ll>, ll> f[], g[];

 int cnt[];

 int main()

 {

     freopen("in.in","r",stdin);

     freopen("out.out","w",stdout);

     int n = ;

     Get_Primes(n);

     for (int i = ; i <= p[]; ++i)

     {

         int  x = p[i];

         while (x <= n) cnt[i] += n / x, x *= p[i];

     }

     f[][make_pair(,)] = ;

     for (int i = ; i <= ; ++i)

     {

         for (map<pair<ll,ll>, ll>::iterator it = f[i - ].begin(); it != f[i - ].end(); it++)

         {

             ll k1 = (*it).first.first, k2 = (*it).first.second;

             for (int j = ; j <= cnt[i]; ++j)

             {

                 ll kx = k1 * (j + ), ky = k2 * (cnt[i] - j + ) , d = Gcd(kx, ky);

                 f[i][make_pair(kx / d, ky / d)] += (*it).second;

             }

         }

     }

     g[][make_pair(,)] = ;

     for (int i = ; i <= p[] - ; ++i)

     {

         for (map<pair<ll,ll>, ll>::iterator it = g[i - ].begin(); it != g[i - ].end(); it++)

         {

             ll k1 = (*it).first.first, k2 = (*it).first.second;

             for (int j = ; j <= cnt[i + ]; ++j)

             {

                 ll kx = k1 * (j + ), ky = k2 * (cnt[i + ] - j + ), d = Gcd(kx, ky);

                 g[i][make_pair(kx / d, ky / d)] += (*it).second;

             }

         }

     }

     for (map<pair<ll,ll>, ll>::iterator it = g[p[] - ].begin(); it != g[p[] - ].end(); it++)

     {

         ll x = (*it).first.first, y = (*it).first.second;

         mp[node(x, y)] += (*it).second;

     }

     ll res = ;

     for (map<pair<ll,ll>, ll>::iterator it = f[].begin(); it != f[].end(); it++)

     {

         ll x = (*it).first.first, y = (*it).first.second;

         res += (*it).second * mp[node(y, x)];

     }

     cout << res /  << endl;

     return ;

 }

答案：543194779059

巴特西

Split Divisibilities (Project Euler 598)

最新文章

热门文章