标签归档:质因数分解

LightOJ – 1236 Pairs Forming LCM

Pairs Forming LCM

把n进行质因数分解,设n的某个质因子为p,其指数为cnt.
对i和j包含的相同质因子p,设指数分别为a,b,由于LCM(i,j)=n,则有cnt=max(a,b).
a,b共有2*(cnt+1)-1种方案(乘以2是a,b互换,减1是剔除a=b的重复情况)

之后由乘法原理,得到了(i,j)的方案数res, 但其中包括了i>j的部分.i<j 和 i>j是对称的, 则 (res+1)/2就是题目要求的了.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ll long long
using namespace std;
const int maxn = 1e7;
bool v[maxn + 1];
vector<int> prime;
void primes() {
  v[0] = v[1] = 1;
  for (int i = 2; i <= maxn; ++i) {
    if (!v[i]) {
      prime.push_back(i);
      for (int j = i; j <= maxn / i; ++j) {
        v[i * j] = 1;
      }
    }
  }
}

ll divide(ll n) {
  ll res = 1;
  for (int i = 0; i < prime.size(); ++i) {
    if (prime[i] > n) break;
    int t = 0;
    if (n % prime[i] == 0) {
      while (n % prime[i] == 0) {
        t++;
        n /= prime[i];
      }
      res *= 2 * (t + 1) - 1;
    }
  }
  if (n > 1) res *= 3;

  return (res + 1) / 2;
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T, kase = 0;
  primes();
  cin >> T;
  while (T--) {
    long long n;
    cin >> n;
    printf("Case %d: %lld\n", ++kase, divide(n));
  }
  return 0;
}

LightOJ – 1341 Aladdin and the Flying Carpet

题目链接

因为有4000个case, 直接累计约数的话会超时,每个case的复杂度达10^6.

用算术基本定理的推论,则要先质数打表,不然对每个数进行质因数分解时还要一边求质数,会造成很多不必要的循环(质数之间有很多间隔).

奇怪的是后面剔除宽为1~b的时候,复杂度应该也为10^6,这样却不超时了.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int v[1000005];
int p[1000005];
int k;
void primes(int n){
  for(int i=2;i<=n;++i){
    if(v[i]) continue;
    p[++k]=i;
    for(int j=i;j<=n/i;++j) v[i*j]=1;
  }
}

ll divide(ll n){
    ll res=1;
    for(int i=1;i<=k;++i){
      int t=0;
      if(n<p[i]) break;
      while(n%p[i]==0){
        n/=p[i];
        t++;
      }
      res*=(t+1);
    }
    if(n>1) res*=2;
    return res;
}

int main() {
  int T,kase=0;
  cin>>T;
  primes(1000000);
  while(T--){  
    ll a,b;
    cin>>a>>b;
    ll ans=divide(a)/2;
    if(b>=sqrt(a)) ans=0;
    else{
       for(int i=1;i<b;++i){
         if(a%i==0) ans--;
      }
    }
    printf("Case %d: %lld\n",++kase,ans);

  }
  return 0;
}

POJ 1845- Sumdiv


题目链接:POJ1845

题意:求\(A^B\)的所有约数之和\(\mod 9901\), \(1 \le A,B \le 5*10^7 \).

把A分解质因数,可以得到约数和为:
\((1+p_1+p_1^2+...+p_1^{B*c_1})*(1+p_2+p_2^2+...+p_2^{B*c_2})*...*(1+p_n+p_n^2+...+p_n^{B*c_n})\)

其中每一项都是等比数列求和:\( \frac{p_i^{B*c_i+1}-1}{p_i-1}\),如果分母逆元存在,则用乘以逆元代替除法运算,如果不存在,有\(p_i\mod 9901=1\),则:
\( 1+p_i+p_i^2+...+p_i^{B*c_i}\equiv 1+1+1^2+...+1^{B*c_i}\equiv B*c_i+1 \pmod {9901} \).

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int c[20],p[20];
int m;
void divide(int a){
    m=0;
    for(int i=2;i<=sqrt(a);++i){
      if(a%i==0){
        p[++m]=i;
        c[m]=0;
        while(a%i==0){
          a/=i;
          c[m]++;
        }
      }
    }
    if(a>1){
      p[++m]=a;
      c[m]=1;
    }
}

int quickpow(int mod,int a,int n){
  int res=1;
  while(n){
    if(n&1) res=(ll)res*a%mod;
    a=(ll)a*a%mod;
    n>>=1;
  }
  return res;
}

int inv(int mod,int x){
  return quickpow(mod,x,mod-2);
}

int main(){
  int a,b;
  const int mod=9901;
  cin>>a>>b;
  divide(a);
  int ans=1;
  for(int i=1;i<=m;++i){
    int x=(quickpow(mod,p[i],(ll)b*c[i]+1)-1+mod)%mod;
    int y=(p[i]-1)%mod;
    if(y){
      ans=(ll)ans*(x*inv(mod,y))%mod;
    }
    else{
      ans=ans*((ll)b*c[i]+1)%mod;  
    }
  }
  cout<<ans<<endl;
  return 0;
}

CH 3101-阶乘分解

题目:

给定整数 N(1≤N≤10^6),试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的p_i 和 c_i 即可。

思路:
如果直接分别对2~N分解质因数,再将结果合成,那么时间复杂度过高会超时。显然N!的质因数不会超过N,那么先求出不超过N的所有素数p,再分别求出其在N!中的次数。对每一个素数p,其在N!中的次数等于在1~N中的次数之和。1~N中能被p整除的有⌊N/p⌋个数,能被p^2整除的有⌊N/p^2⌋个数(也就是说此时p的次数至少有⌊N/p⌋+⌊N/p^2⌋,其中⌊N/p^2⌋不必乘以2,因为被p^2整除的数也被p整除,而此前已经统计过一次p),以此类推,p的次数就有⌊N/p⌋+⌊N/p^2⌋+⌊N/p^3⌋+……+⌊N/p^⌊log(N)/log(p)⌋⌋. 每如此计算一次,时间复杂度为O(logN),则总复杂度为O(NlogN).

代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 1000005

int v[MAX_N];
int prime[MAX_N];
int c[MAX_N];

int m;
void primes(int n) {
  m = 0;
  memset(v, 0, sizeof(v));
  memset(prime, 0, sizeof(prime));
  for (int i = 2; i <= n; i++) {
    if (v[i] == 0) {
      v[i] = i;
      prime[++m] = i;
    }
    for (int j = 1; j <= m; j++) {
      if (prime[j] > v[i] || prime[j] > n / i) {
        break;
      }
      v[i * prime[j]] = prime[j];
    }
  }
}

int main() {
  int n;
  cin >> n;
  primes(n);
  for (int i = 1; i <= m; i++) {
    long long p = prime[i]; //最后一次极限情况相乘可能溢出所以用ll,有点坑,找了好久
    int t = 0;
    while (n/p) {
      t += n / p;
      p *= prime[i];
    }
    c[i] = t;
  }
  for (int i = 1; i <= m; i++) {
    printf("%d %d\n", prime[i], c[i]);
  }

  return 0;
}