Algoogle

Algorithm for Programming Contest

AOJ 1060 No Story

Category: AOJ Tag: math

No Story

問題概要


LCMがL(<=1,000,000,000,000)になる2整数a,b(a<=b)の組の数

解法


pは素数とする.
このときある2数のLCMがLになるには, 各pについて2数のどちらかは を含む.
もう片方のpは0からe乗のいずれかになる.
その組合せを考えれば良い.

コード


(1060.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

int p[1<<20];
vector<long long> ps;
long long n;

long long solve()
{
        long long ans = 1;
        for(auto &e: ps) {
                if(n == 1) break;
                long long cnt = 0;
                while(n%e==0) {
                        cnt++;
                        n /= e;
                }
                ans *= cnt*2+1;
        }
        if(n > 1) ans *= 3;
        return (ans+1)/2;
}

void genp()
{
        p[0] = p[1] = 1;
        for (int i = 0; i < 1<<20; i++)
                if(!p[i]) {
                        ps.push_back(i);
                        for (int j = i+i; j < 1<<20; j+=i) p[j] = 1;
                }
}

int main()
{
        genp();
        while(cin >> n, n) cout << solve() << endl;
        return 0;
}

Comments