AOJ 整数論 素因数分解, べき乗, 最小公倍数, オイラーのφ関数, 拡張ユークリッドの互除法

##前回の続き
[全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索](https://qiita.com/RubyLrving/items/449048d8a8ce9ae14d7c)

##Library - NTL
###NTL_1_A
###[素因数分解](https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n;
    cin >> n;
    
    cout << n << ':';
    int m=n, l=2;
    while(l*l<=m){
        if(m%l==0){
            cout << ' ' << l;
            m=m/l;
        }else{
            l++;
        }
    }
    if(m != 1) cout << ' ' << m;
    cout << endl;

    return 0;
}
```

###NTL_1_B
###[べき乗](https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_B)
###解説
[「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

ll modpow(ll a, ll n, ll mod){
    long long res = 1;
    while(n>0){
        if(n&1) res = res * a % mod;
        a = a * a % mod;
        n = n>>1;
    }
    return res;
}

int main(int argc, const char * argv[]) {
    int m, n;
    cin >> m >> n;
    cout << modpow(m, n, 1000000007) << endl;
    return 0;
}
```

###NTL_1_C
###[最小公倍数](https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_C)
整数a, bの最小公倍数は、(a * b) / gcd(a. b)である。
aとbの積をaとbの最小公約数で割った値になります。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int gcd(int x, int y){
    if(x<y) swap(x, y);
    while(y>0){
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int dfs(vector<int> vec, int index){
    if(index+1==vec.size()-1){
        return (vec[index]*vec[index+1])/gcd(vec[index], vec[index+1]);
    }
    return (vec[index]*dfs(vec, index+1))/gcd(vec[index], dfs(vec, index+1));
}

int main() {
    int n;
    cin >> n;

    vector<int> vec(n);
    rep(i, n){
        cin >> vec[i];
    }

    cout << dfs(vec, 0) << endl;

    return 0;
}
```

###NTL_1_D
###[オイラーのφ関数](https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D)
###解説
[オイラーのφ関数](http://www.prefield.com/algorithm/math/euler_phi.html)
今の自分では理解できない。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int EulerPhi(int n) {
  if (n == 0) return 0;
  int ans = n;
  for (int x = 2; x*x <= n; ++x) {
    if (n % x == 0) {
      ans -= ans / x;
      while (n % x == 0) n /= x;
    }
  }
  if (n > 1) ans -= ans / n;
  return ans;
}

int main() {
    int n;
    cin >> n;

    cout << EulerPhi(n) << endl;
    return 0;
}
```

###NTL_1_E
###[拡張ユークリッドの互除法](https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E)
[拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜](https://qiita.com/drken/items/b97ff231e43bce50199a)
今の自分では理解できない。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main() {
    int a, b;
    cin >> a >> b;

    long long x, y;
    extGCD(a, b, x, y);
    cout << x << ' ' << y << endl;

    return 0;
}
```