首页 > 代码库 > [UVA10139]Factovisors（数论，质因数）

[UVA10139]Factovisors（数论，质因数）

2024-08-15 17:44:30   217人阅读

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1080

题意：问n!能否被m整除。

给m分解质因数，用这些质因数以及他们的幂分别去除n，直到质因数的幂大于n。统计每一次的商，假如存在一个商小于质因数在m中出现的次数，说明n!不能被m整除了。uDEBUG好好用，没开LL一直wa，结果去查一下就查出来了。

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 typedef long long LL; 5 LL n, m; 6 vector<LL> p, a; 7  8 void f(LL x) { 9   p.clear(); a.clear();10   LL xx = (LL)sqrt(x) + 1;11   for(LL i = 2; i < xx; i++) {12     if(x % i == 0) {13       p.push_back(i);14       LL cnt = 0;15       while(x % i == 0) {16         x /= i;17         cnt++;18       }19       a.push_back(cnt);20     }21   }22   if(x > 1) {23     p.push_back(x); a.push_back(1);24   }25 }26 27 LL mul(LL x, LL n) {28   LL ret = 1;29   while(n) {30     if(n & 1) ret *= x;31     n >>= 1; x *= x;32   }33   return ret;34 }35 36 int main() {37   //freopen("in", "r", stdin);38   //freopen("out", "w", stdout);39   while(~scanf("%lld%lld",&n,&m)) {40     if(m == 0) {41       printf("%lld does not divide %lld!\n", m, n);42       continue;43     }44     f(m); bool flag = 0;45     for(LL i = 0; i < p.size(); i++) {46       LL cnt = 0;47       LL j = 1;48       LL q = mul(p[i], j++);49       while(n >= q) {50         cnt += (n / q);51         q = mul(p[i], j++);52       }53       if(cnt < a[i]) flag = 1;54       if(flag) break;55     }56     if(!flag) printf("%lld divides %lld!\n", m, n);57     else printf("%lld does not divide %lld!\n", m, n);58   }59   return 0;60 }

 

[UVA10139]Factovisors（数论，质因数）


联系
我们