2014-08-13

POJ 3641: Psudoprime numbers, POJ 1995 : Raising Modulo Numbers

POJ 蟻本

解法

繰り返し二乗をやるだけ．

POJ 3641

bool isPrime(ll x){
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0) return false;
    }
    return true;
}

ll p, a;
int main(){
    for(;;){
        scanf("%lld%lld", &p, &a);
        if(p == 0 && a == 0) return 0;
        ll q = 1, s = a;
        for(int t = p; t > 0; t >>= 1){
            if(t & 1) q = (q * s) % p;
            s = (s * s) % p;
        }
        printf("%s\n", !isPrime(p) && a == q ? "yes": "no");
    }
}

POJ 1995

ll mod_pow(ll a, ll n, ll M){
    if(n == 0) return 1;
    ll p = mod_pow((a * a) % M, n / 2, M);
    return (p * (n & 1 ? a: 1)) % M;
}

int Z, H;
ll M, A[45010], B[45010];
int main(){
    scanf("%d", &Z);
    for(; Z > 0; --Z){
        scanf("%lld%d", &M, &H);
        for(int i = 0; i < H; ++i)
            scanf("%lld%lld", &A[i], &B[i]);
        ll res = 0;
        for(int i = 0; i < H; ++i){
            res = (res + mod_pow(A[i], B[i], M)) % M;
        }
        printf("%lld\n", res);
    }
    return 0;
}

2014-08-13

POJ 3292 : Semi-prime H-numbers

POJ 蟻本

概要

H={4N+1|Nは0以上の整数}とする．この時，Hの元xが1とxの組以外の積で表現できないものをHの素数と呼ぶことにする．h \in Hが与えられたとき，2つのHの素数の積で表すことができるh以下の数の個数を計算する．

解法

素数の列挙は篩を使っていい．
あとは，事前に数え上げる処理を行っておけばいい．

Hの素数の積は1通りでしか表せないと勘違いしていたので，なかなか通らなかった．
実際はそんなことはなく，9 * 111089 = 33 * 30297がその反例．

PKU 3292 Semi-prime H-numbers - 敗戦記を見た．

int n;
ll prime[100000];
bool isnPrime[1000010];
int dp[1000010];
int h;
int main(){
    n = 0;
    for(int i = 5; i <= 1000001; i += 4) if(!isnPrime[i]){
        prime[n] = i;
        ++n;
        for(int j = i * 5; j <= 1000001; j += i * 4)
            isnPrime[j] = true;
    }
    for(int i = 0; i < n; ++i)for(int j = i; j < n && prime[i] * prime[j] <= 1000010; ++j){
        dp[prime[i] * prime[j]] = 1;
    }
    for(int i = 1; i <= 1000001; ++i){
        dp[i] += dp[i-1];
    }
    for(;;){
        scanf("%d", &h);
        if(h == 0) return 0;
        printf("%d %d\n", h, dp[h]);
    }
}

2014-08-12

POJ 3421: X-factor Chains

POJ 蟻本

概要

2^20より小さい正整数Xが与えられる．長さnのX-factor ChainはX_1 < X_2 < ... < X_n = Xで，かつ
X_i | X_{i+1} であるものをいう．
Xの最長のX-factor Chainの長さはいくつか．また，最長のX-factor Chainの個数はいくつあるか．

解法

Xを素因数分解．素因数の冪の合計が長さに，各素因数の重複順列が個数に対応する．

vector<int> sieve_of_eratosthenes(ll n, vector<ll> &prime){
    vector<int> isPrime(n);
    for(ll i = 2; i < n; ++i)
        isPrime[i] = i;
    for(ll i = 2; i < n; ++i)
        if(isPrime[i]){
            prime.push_back(i);
            for(ll j = i * i; j < n; j += i)
                isPrime[j] = 0; 
        }
    return isPrime;
}
ll factorial(ll n){
    ll res = 1;
    while(n > 0) res *= n--;
    return res;
}

vector<ll> prime;
ll X;
int main(){
    sieve_of_eratosthenes(1LL << 20, prime);
    while(~scanf("%lld", &X)){
        ll sum = 0, res;
        vector<ll> v;
        EACH(i, prime){
            if(X <= (*i) * (*i)){
                if(X == *i * *i){
                    v.push_back(2);
                    sum += 2;
                    X = 1;
                }
                if(X != 1){
                    sum ++;
                }
                break;
            }
            if(X % *i == 0){
                ll s = 0;
                while(X % *i == 0){
                    ++s;
                    X /= *i;
                }
                sum += s;
                v.push_back(s);
            }
        }
        res = factorial(sum);
        EACH(i, v)
            res /= factorial(*i);
        printf("%lld %lld\n", sum, res);
    }
    return 0;
}

2014-08-12

POJ 3126: Prime Path

POJ 蟻本

概要

2つの4桁の素数A, Bが与えられる．Aに対して，「どれか一つの桁を書き換えて別の素数にする（ただし，最上位は0に書き換えてはいけない）」という操作を最小何回行えばBにすることができるか．

解法

素数の表を作り，幅優先探索．

bool isntPrime[10000], visited[10000];
int main(){
    memset(isntPrime, 0, sizeof(isntPrime));
    for(int i = 2; i <= 9999; ++i){
        if(isntPrime[i]) continue;
        for(int j = i + i; j <= 9999; j += i)
            isntPrime[j] = true;
    }
    int T;
    scanf("%d", &T);
    for(--T; T >= 0; --T){
        int a, b, res;
        scanf("%d%d", &a, &b);
        queue<pair<int, int> > Q;

        res = -1;
        memset(visited, 0, sizeof(visited));
        Q.push(make_pair(a, 0));
        visited[a] = true;
        while(!Q.empty()){
            int t = Q.front().first, s = Q.front().second;
            Q.pop();
            if(t == b){
                res = s; break;
            }
            for(int i = 1; i <= 1000; i *= 10) for(int j = 0; j <= 9; ++j){
                if(i == 1000 && j == 0) continue;
                int nt = t + (j - t / i % 10) * i;
                if(visited[nt] || isntPrime[nt]) continue;
                visited[nt] = true;
                Q.push(make_pair(nt, s + 1));
            }
        }
        if(res == -1){
            printf("Impossible\n");
        }
        else{
            printf("%d\n", res);
        }
    }
    return 0;
}

2014-08-11

POJ 1930: Dead Fraction

POJ 蟻本

概要

小数が与えられる．循環小数と見たとき，分母が最も小さくなる分数表示を求める．

解法

循環する区間を仮定して分数に直すという操作を繰り返す．
n桁の循環する小数は，cを循環する部分を表す整数とすると，c/(10^n-1)で得られる．

typedef unsigned long long ull;

ull gcd(ull x, ull y){
    return y ? gcd(y, x%y): x;
}

string s;
int main(){
    for(;;){
        cin >> s;
        if(s == "0") return 0;
        s = s.substr(2, s.size()-5);
        ull p, q, v, w, g;
        p = q = ULLONG_MAX;
        v = 1; w = 1;
        for(int i = 0; i < s.size(); ++i) w *= 10;
        for(int i = 0; i < s.size(); ++i){
            ull a, b, c, d;
            if(i == 0) a = 0;
            else       sscanf(s.substr(0, i).c_str(), "%llu", &a);
            b = v;
            sscanf(s.substr(i).c_str(), "%llu", &c);
            d = w - 1;

            g = gcd(a, b);
            a /= g; b /= g;
            g = gcd(c, d);
            c /= g; d /= g;
            g = gcd(c, v);
            c /= g;
            d *= v / g;

            g = gcd(b, d);
            a = a * (d / g) + c * (b / g);
            b = b / g * d;
            g = gcd(a, b);
            a /= g; b /= g;
            // cerr << ">" << a << "/" << b << endl;
            if(b < q){
                p = a; q = b;
            }

            v *= 10;
            w /= 10;
        }
        cout << p << "/" << q << endl;
    }
}

2014-08-10

POJ 2395: Out of Hay

POJ 蟻本

概要

ある頂点から，他の別の頂点へ横切る辺の重みの最大値が最小になるように移動する．
この時，横切る辺の重みの最大値はいくつか．

解法

最小全域木を求め，その中でもっとも重みの大きい辺を出力．

struct UnionFind{
    vector<int> parent, rank;
    UnionFind(int n) : parent(n,-1), rank(n, 0) { }
    int find(int x){
        if(parent[x] == -1) return x;
        else return (parent[x] = find(parent[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(rank[x] < rank[y])
            parent[x] = y;
        else
            parent[y] = x;
        if(rank[x] == rank[y])
            ++rank[x];
        return true;
    }
};

typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { }
};
bool operator<(const Edge &a, const Edge &b){
    return a.weight > b.weight;
}
typedef vector<Edge> Edges;

pair<Weight, Edges> kruskal_e(Edges &edges, int n){
    sort(ALL(edges)); reverse(ALL(edges));
    int sz = edges.size();
    UnionFind uf(n);
    Weight total = 0;
    Edges F;
    EACH(i, edges){
        if(uf.unite(i->from, i->to)){
            total += i->weight;
            F.push_back(*i);
        }
    }
    return make_pair(total, F);
}

int N, M;

int main(){
    scanf("%d%d", &N, &M);
    Edges es;
    for(int i = 0; i < M; ++i){
        int a, b, l;
        scanf("%d%d%d", &a, &b, &l);
        es.push_back(Edge(a-1, b-1, l));
    }
    Edges res = kruskal_e(es, N).second;
    reverse(ALL(res));
    printf("%d\n", res[0].weight);
    return 0;
}

2014-08-10

POJ 2377: Bad Cowtractors

概要

最大全域木を求める．

解法

辺の正負を反転して最小全域木を求める．

struct UnionFind{
    vector<int> parent, rank;
    UnionFind(int n) : parent(n,-1), rank(n, 0) { }
    int find(int x){
        if(parent[x] == -1) return x;
        else return (parent[x] = find(parent[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(rank[x] < rank[y])
            parent[x] = y;
        else
            parent[y] = x;
        if(rank[x] == rank[y])
            ++rank[x];
        return true;
    }
};

typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { }
};
bool operator<(const Edge &a, const Edge &b){
    return a.weight > b.weight;
}
typedef vector<Edge> Edges;

pair<Weight, Edges> kruskal_e(Edges &edges, int n){
    sort(ALL(edges)); reverse(ALL(edges));
    int sz = edges.size();
    UnionFind uf(n);
    Weight total = 0;
    Edges F;
    EACH(i, edges){
        if(uf.unite(i->from, i->to)){
            total += i->weight;
            F.push_back(*i);
        }
    }
    return make_pair(total, F);
}

int N, M;
Edges es;
int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < M; ++i){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        es.push_back(Edge(a, b, -c));
    }
    pair<Weight, Edges> p = kruskal_e(es, N + 1);
    printf("%d\n", p.second.size() == N - 1 ? -p.first: -1);
    return 0;
}