当前位置：首页 > news >正文

UVA - 1635 Irrelevant Elements（质因数分解）

news 来源：原创 2024/5/4 11:08:42

传送门

因为组合数的计算公式是递推过来的，那么首先对 $m$ 质因数分解，接着我们对组合数的计算中间变量每次质因数分解，即分子 $n - i + 1$ 分解的质因数都加一， $i$ 分解的质因数都减一，然后遍历 $m$ 的所有质因数，当且仅当组合数的所有质因数个数均大于等于 $m$ 的个数才可以作为答案

注意几个细节：一是 $n$ 一开始要先减一最后的答案都加一；二是分解质因数的过程中最后一步要特判是否分解到 $1$ ，因为该数可能是大于其根号的一个质数

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

map<int,int> mp1,mp2;
vector<int> fac;
set<int> ans;

void add_fac(int x,int d){
    int y=sqrt(x+0.5);
    for(int i=2;i<=y;i++){
        if(x%i==0){
            while(x%i==0){
                x/=i;
                mp2[i]+=d;
            }
        }
        if(x==1) break;
    }
    if(x>1) mp2[x]+=d;
}

bool check(){
    for(auto i: fac){
        if(mp2[i]<mp1[i]) return false;
    }
    return true;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    while(cin>>n>>m){
        mp1.clear(),mp2.clear(),ans.clear(),fac.clear();
        int p=sqrt(m+0.5);
        for(int i=2;i<=p;i++){
            if(m%i==0){
                fac.push_back(i);
                while(m%i==0){
                    m/=i;
                    mp1[i]++;
                }
            }
            if(m==1) break;
        }
        if(m>1){  //这里最容易忘记
            fac.push_back(m);
            mp1[m]++;
        }
        n--;
        //for(auto i: fac) cout<<i<<endl;
        for(int i=1;i<=(n>>1);i++){
            add_fac(n-i+1,1);
            add_fac(i,-1);
            if(check()){
                ans.insert(i);
                ans.insert(n-i);
            }
        }
        cout<<ans.size()<<endl;
        bool ok=0;
        for(auto i: ans){
            if(!ok){
                ok=1;
                cout<<i+1;
            }else cout<<" "<<i+1;
        }
        cout<<endl;
    }
    return 0;
}