uva10791 uva10780（分解质因数）

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1732

给定我们一个n，要找到两个数的集合，使得这些书的最小公倍数（LCM）为n，由于有很多这样的集合，我们要选出总和最小的，而且也只要输出总和就行了

数的最大公倍数是怎么求的？是每个质因数指数最大的那个相乘而来的。

通过最小公倍数的求法，我们可以看出最小公倍数取决于每个质因子在各个数中的最高次。

如果要总和最小，我们要把同一个质因数放到一个整数里面

因为a*b>a+b

比如12 = 3 * 2^2 a = 3, b = 2 a * b > a + b 即2*3 > 2 + 3

所以最终的结果是3 * 4 = 12，此时和最小，为7

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <algorithm>

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <map>

 #include <set>

 #include <string>

 #include <math.h>

 using namespace std;

 #pragma warning(disable:4996)

 typedef long long LL;

 const int INF = <<;

 /*

 */

 int main()

 {

     LL n, i, m, k = ;

     LL ans;

     while (scanf("%lld", &n), n)

     {

         int nn = n;

         ans = ;

         m = sqrt(n) + 0.5;

         int cnt = ;

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

         {

             if (n%i == )

             {

                 int t = ;

                 while (n%i == )

                 {

                     t *= i;

                     n /= i;

                 }

                 ans += t;

                 cnt++;

             }

         }

         if (n > )

         {

             ans += n;

             cnt++;

         }

         if (cnt == )//这是只有单独一个数的情况

             ans += ;

         else if (cnt == )//这是n为1的情况

             ans += ;

         printf("Case %lld: %lld\n", k++,ans);

     }

     return ;

 }

uva10780 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1721

给定m 和 n

求最大的x 使得 n % m^x ==0，

思路：将m分解质因数，相同的质因数合并，那么可以得到 p1^a1 , p2^a2..pn^an ，我们只要求出n!中质因数pi 是pi^ai的多少次幂，然后最小的那个次幂就是答案

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <algorithm>

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <map>

 #include <set>

 #include <string>

 #include <math.h>

 using namespace std;

 #pragma warning(disable:4996)

 typedef long long LL;

 const int INF = <<;

 /*

 */

 int a[ + ];

 int main()

 {

     int t, n, m;

     scanf("%d", &t);

     for (int k = ; k <= t; ++k)

     {

         int ans = INF;

         scanf("%d%d", &m, &n);

         int limit = sqrt(m) + 0.5;

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

         {

             if (m%i == )

             {

                 int cnt = ;

                 while (m%i == )

                 {

                     cnt++;

                     m /= i;

                 }

                 int tmp = ;

                 for (int j = ; j <= n; ++j)

                 {

                     int x = j;

                     while (x % i == )

                     {

                         x /= i;

                         tmp++;

                     }

                 }

                 ans = min(ans, tmp/cnt);

             }

         }

         if (m > )

         {

             int tmp = ;

             for (int j = ; j <= n; ++j)

             {

                 int x = j;

                 while (x % m == )

                 {

                     x /= m;

                     tmp++;

                 }

             }

             ans = min(ans, tmp);

         }

         if (ans ==  || ans==INF)

             printf("Case %d:\nImpossible to divide\n",k);

         else

             printf("Case %d:\n%d\n", k, ans);

     }

     return ;

 }

巴特西

uva10791 uva10780（分解质因数）

最新文章

热门文章