牛客アルゴリズム周周練4 C題——階乗二分+階乗分解質因子
たとえば、100=2*2*5*5です.ここではmapという容器を用い,firstは各質量因子,2と5,secondが出現した回数であり,100を分解した後,mapに存在するのは{2,2,}と{5,2}である.そしてmidの階乗が100の倍数かどうかを判断する必要があります.mid次第です.中質因子2の個数>=2,5の個数>=2である.
(2)ではn!中質因子の個数をどう判断するか.
n!中質因子pの個数、1−nに質因子pの数を含む個数.n!少なくとも1つの質量因子pを含む個数はn/pであり、少なくとも2つを含む個数はn/p^2である......
例えばmid=8、判断8!中素因数2の個数.まずは8!中には2 4 6 8の4つの数が2を除くことができて、この数は8/2=4です;2を除いて8!中は、1 2 3 4になり、そのうち2と4は2を除くことができ、この数は4/2=2です.2を除いて2は1つしかありません.この数は2/2=1です.だから8!中質因子2の個数は4+2+1=7である.(3)コード:
#include "bits/stdc++.h"
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
// #define _DEBUG
typedef long long ll;
const int maxn = 2e5 + 7;
const int INF = INT_MAX; // 0x7fffffff
int t,p;
map<int,int> mp;
void init(int p){ // map
mp.clear();
for (int i = 2; i*i <= p; i++) {
// i*i ， p p
while (p % i == 0) {
mp[i] ++;
p /= i;
}
if (p == 1) {
break;
}
}
if (p != 1) { //p
mp[p] = 1;
}
}
bool ok(int mid){
for (map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) {
int prime = it->first, num = it->second;
int cnt = 0, n = mid; //cnt
while (n) {
cnt += n / prime;
n /= prime;
}
if (cnt < num) {
return false;
}
}
return true;
}
int main(){
#ifdef _DEBUG
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while (t--) {
cin>>p;
init(p);
int l = 1, r = p;
int ans = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
if (ok(mid)) {
r = mid - 1;
ans = mid; // ans
}else{
l = mid + 1;
}
}
cout<<ans<<endl;
}
return 0;
}
(4)遭遇した問題:p分解質因子の場合、i*i<=pであることに注意してください.そうでないとTLEになります.これはエー氏ふるい法に似た小さなテクニックで、具体的には以下のリンクを見ることができます.オーラふるい法の2分の中で、r=mid-1ではなく、r=midが死んで循環するので、直接mid+1とmid-1のように、同時に最後のlあるいはrは最後の答えではないかもしれません.ansを使います答えを更新するたびに.
2、同様に質因子を分解する方法であるが、gcd(1)最大公因子Greatest Common Divisorという関数を用いて劉汝佳大神の「アルゴリズムコンテスト入門経典」で述べた.転々相殺法.
int gcd(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}
(2)pが1または素数であれば、直接pを出力する.
if (p == 1 || isPrime(p)) {
cout<<p<<endl;
}else{
for (int i = 2; ; i++) {
if (gcd(i,p) != 1) {
p /= gcd(i,p);
if (p == 1) {
cout<<i<<endl;
break;
}
if (i < p && isPrime(p)) {
cout<<p<<endl;
break;
}
}
}
}
iは2から遍歴し、iとpに最大公因子がある場合、p/=gcd(i,p)、p=1である場合、このiを直接出力する.このときi
#include "bits/stdc++.h"
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
const int maxn = 1e4 + 7;
const int INF = INT_MAX;
// #define _DEBUG
int t,p;
bool isPrime(int p){
if(p == 1) return false;
for (int i = 2; i*i <= p; i++) {
if(p % i == 0) return false;
}
return true;
}
int gcd(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}
int main(){
#ifdef _DEBUG
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while (t--) {
cin>>p;
if (p == 1 || isPrime(p)) {
cout<<p<<endl;
}else{
for (int i = 2; ; i++) {
if (gcd(i,p) != 1) {
p /= gcd(i,p);
if (p == 1) {
cout<<i<<endl;
break;
}
if (i < p && isPrime(p)) {
cout<<p<<endl;
break;
}
}
}
}
}
return 0;
}