about 4 years ago

到這麼多COT題目,也來跟風(X

問題:
給你一個n( ),問是否存在使得。題目會有多筆詢問。

題解:

以下表n的因數個數。

首先可以把展開

假如有解,那麼必然存在

我們可以試著去枚舉
可以觀察到,所以可以先從的因數下手:

  1. 因數分解
  2. BFS遍歷

所以我們可以得到一個集合:

可以順便注意到,這可以保證時空複雜度

然後再由A生成一個集合

同樣的,

接下來就對裡面的元素做枚舉
去檢查的因數分解。
假如把分解後得到
並且,那麼還原就是一解

#include<cstdio>
#include<cstdlib>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long int int64;
typedef set<int64>::iterator siit;
bool seive[100001] = {0};
vector<int64> primes;
bool isprime(int64 a){
    if(a < 100000) return seive[a] == false;
    for(int64 lx = 2;lx*lx <= a;lx++)
        if(a%lx == 0)
            return false;
    return true;
}
vector<pair<int64,int> > getdrc(int64 inp){
    vector<pair<int64,int> > ret;
    for(int lx = 0;lx < primes.size() and primes[lx] <= inp; lx++){
        int ecnt = 0;
        while(inp%primes[lx] == 0)
            inp /= primes[lx], ecnt++;
        if(ecnt)
            ret.push_back(pair<int64,int>(primes[lx], ecnt));
    }
    if(inp > 1)
        ret.push_back(pair<int64,int>(inp,1));
    return ret;
}
set<int64> getdivs(int64 inp){
    set<int64> divs;
    vector<pair<int64,int> > drc = getdrc(inp);
    divs.insert(1);
    for(int lx = 0;lx < drc.size();lx++){
        set<int64> si;
        int64 drc0 = drc[lx].first;
        int drc1 = drc[lx].second;
        for(siit it = divs.begin(); it != divs.end(); it++){
            int64 ee = 1;
            for(int64 xx = 0; xx <= drc1; xx++, ee *= drc0)
                si.insert((*it)*ee);
        }
        divs.clear();
        for(siit it = si.begin(); it != si.end(); it++)
            divs.insert(*it);
    }
    return divs;
}

int main(){
    int64 inp;
    seive[1] = true;
    for(int lx = 2;lx < 100000;lx++){
        if(seive[lx] == false){
            primes.push_back((int64)lx);
            for(int ly = 2;ly*lx < 100000;ly++)
                seive[lx*ly] = true;
        }
    }
    while(1){
        scanf("%lld", &inp);
        if(inp == 0) break;
        set<int64> divs = getdivs(inp); 
        //printf("divisores: ");
     /*for(siit it = divs.begin(); it != divs.end(); it++)
            printf("%lld ", *it);
        printf("\n");*/

        vector<int64> Aset;
        for(siit it = divs.begin(); it != divs.end(); it++)
            if(isprime((*it)+1))
                Aset.push_back(*it);

        /*printf("Aset: ");
        for(int lx = 0;lx < Aset.size(); lx++){
            printf("%lld ", Aset[lx]);
        }
        printf("\n");*/
        set<int64> Tset; Tset.insert(1);
        for(int lx = 0;lx < Aset.size();lx++){
            set<int64> TTset;
            for(siit it = Tset.begin(); it != Tset.end();it++){
                TTset.insert(*it);
                if(inp%((*it)*Aset[lx]) == 0)
                    TTset.insert((*it)*Aset[lx]);
            }
            Tset.clear(); Tset.insert(1);
            for(siit it = TTset.begin(); it != TTset.end(); it++)
                Tset.insert(*it);
        }
        /*printf("Tset: ");
        for(siit it = Tset.begin(); it != Tset.end(); it++)
            printf("%lld ", *it);
        printf("\n");*/
        // N/T part
     bool ok = false;
        int64 N = inp;
        for(siit it = Tset.begin();it != Tset.end() and not ok; it++){
            int64 T = *it;
            //printf("prc on %lld\n", *it);
         // assert T | N
         vector<pair<int64,int> > ddrc = getdrc(N/T);
            //printf("N/T = %lld, drc size = %d\n", N/T, (int) ddrc.size());
         int64 mut = 1;
            for(int lx = 0;lx < ddrc.size();lx++){
                mut *= (ddrc[lx].first-1);
            }

            if(T%mut != 0)
                continue;
            
            T /= mut;
            // Check is T = phi(square free) or not
         // if q in ddrc, then p-1 should not divide T now.
         set<int64> inddrc;
            for(int lx = 0;lx < ddrc.size();lx++)
                inddrc.insert(ddrc[lx].first);

            set<int64> gen; gen.insert(1);
            for(int lx = 0;lx < Aset.size();lx++){
                if(inddrc.count(Aset[lx]+1))
                    continue;
                set<int64> tmp;
                for(siit it = gen.begin(); it != gen.end(); it++){
                    tmp.insert(*it);
                    if(T%((*it)*Aset[lx]) == 0)
                        tmp.insert((*it)*Aset[lx]);
                }
                gen.clear(); gen.insert(1);
                for(siit it = tmp.begin(); it != tmp.end(); it++)
                    gen.insert(*it);
            }
            if(gen.count(T))
                ok = true;
        }
        puts(ok ? "Yes":"No");
    }
    return 0;
}

BFS code頗長,不過其實有DFS做法(而且超短,不需要建立A集合和B集合)。

← 我的第一個Online Judge 平方和為質數 →
 
comments powered by Disqus