教育的だと思ったのでメモだけ。
問題概要
整数 が与えられる。 以上 未満の整数 であって
を満たすものの個数を求めよ。
解法
の最大公約数を として のオイラー関数値が答え。
#include <iostream> #include <sstream> #include <cstdio> #include <cstdlib> #include <cmath> #include <ctime> #include <cstring> #include <string> #include <vector> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <numeric> #include <utility> #include <iomanip> #include <algorithm> #include <functional> #include <unordered_map> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } #define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i) template<class T> ostream& operator << (ostream &s, set<T> P) { EACH(it, P) { s << "<" << *it << "> "; } return s << endl; } template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) { EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; } template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); } template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); } template<class T, class V> typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) { t = v; } template<class T, class V> typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){ for (auto &e : t) fill(e, v); } vector<pair<long long, long long> > prime_factorize(long long n) { vector<pair<long long, long long> > res; for (long long p = 2; p * p <= n; ++p) { if (n % p != 0) continue; int num = 0; while (n % p == 0) { ++num; n /= p; } res.push_back(make_pair(p, num)); } if (n != 1) res.push_back(make_pair(n, 1)); return res; } long long GCD(long long x, long long y) { if (y == 0) return x; else return GCD(y, x % y); } long long a, m; long long solve() { long long g = GCD(a, m); m /= g; long long res = m; //COUT(res); auto pf = prime_factorize(m); //COUT(pf); for (auto p : pf) res /= p.first, res *= p.first-1; return res; } int main() { //ios::sync_with_stdio(false); //cin.tie(0); int T; cin >> T; for (int _ = 0; _ < T; ++_) { cin >> a >> m; cout << solve() << endl; } }