Submission #56646456

---

Source Code Expand

#include <bits/stdc++.h>

#define fir first
#define sec second
#ifdef LOCAL
#define dbg(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << '\n'
#define dpi(x, y) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << " ; " << "the " << #y << " = " << y << '\n'
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args)
#else
#define dbg(x) void()
#define dpi(x, y) void()
#define dbgf(fmt, args...) void()
#endif

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vpii = vector<pii>;

bool Mbe;
constexpr int MOD = 998244353;
template<typename T> T add(T a, T b, T p = MOD) { return (a + b >= p) ? (a + b - p) : (a + b); }
template<typename T> T del(T a, T b, T p = MOD) { return (a - b < 0) ? (a - b + p) : (a - b); }
template<typename T> T mul(T a, T b, T p = MOD) { return 1ll * a * b % p; }
template<typename T> T cadd(T &a, T b, T p = MOD) { return a = add(a, b, p); }
template<typename T> T cdel(T &a, T b, T p = MOD) { return a = del(a, b, p); }
template<typename T> T cmul(T &a, T b, T p = MOD) { return a = mul(a, b, p); }
template<typename T> bool cmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> bool cmin(T &a, T b) { return a > b ? a = b, true : false; }

namespace FastIO {
	constexpr int LEN = 1 << 20;
	char in[LEN + 1], out[LEN + 1];
	char *pin = in, *pout = out, *ein = in, *eout = out + LEN;

	char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
	void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
	void Flush() { fwrite(out, 1, pout - out, stdout); pout = out; }

	template<typename T> T Read() {
		T x = 0; int f = 1; char ch = gc();
		while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return x * f;
	}
	template<typename T> void Write(T x, char c) {
		static char stk[40]; int tp = 0;
		if (x < 0) pc('-'), x = ~x + 1;
		do stk[tp++] = x % 10 + 48, x /= 10; while (x);
		while (tp --) pc(stk[tp]); pc(c); return;
	}
	void Read(char *s) {
		char ch = gc();
		while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
			(ch >= '0' && ch <= '9'))) ch = gc();
		while ((ch != EOF) && ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ||
			(ch >= '0' && ch <= '9'))) *s = ch, s ++, ch = gc();
		*s = '\0'; return;
	}
	void Write(char *s) {
		while (*s != '\0') pc(*s), s ++; return;
	}
	void Puts(char *s) {
		Write(s), pc('\n'); return;
	}
}

#define getchar FastIO::gc
#define putchar FastIO::pc
#define Flush FastIO::Flush
#define Read FastIO::Read
#define Write FastIO::Write
#define Puts FastIO::Puts

constexpr int N = 1e6 + 5;
int n, q, a[N], b[N], phi[N];
vector<int> pri, factor[N];
map<int, int> his;
bool vis[N];

void Init() {
	phi[1] = 1;
	for (int i = 2; i <= n; i ++) {
		if (!vis[i]) pri.emplace_back(i), phi[i] = i - 1;
		for (auto j : pri) {
			if (1ll * i * j > n) break; vis[i * j] = true;
			if (!(i % j)) { phi[i * j] = phi[i] * j; break; }
			phi[i * j] = phi[i] * phi[j];
		}
	}
	for (auto p : pri)
		for (int i = p; i <= n; i += p)
			factor[i].emplace_back(p);
	return;
}
int Gcd(int n, int a) {
	int d = 1, g;
	while ((g = __gcd(a, n)) ^ 1) d *= g, n /= g;
	return d;
}
ll Pow(ll a, ll b, ll p) {
	ll ans = 1;
	for (; b; b >>= 1, a = (i128)a * a % p)
		if (b & 1) ans = (i128)ans * a % p;
	return ans;
}
pair<ll, vector<int>> Get_Phi(int a, int b) {
	vector<pair<int, int>> fa, fb;
	ll phi = 1ll * a * b; vector<int> vc;
	for (auto p : factor[a]) {
		fa.emplace_back(p, 0);
		while (!(a % p)) fa.back().sec ++, a /= p;
	}
	for (auto p : factor[b]) {
		fb.emplace_back(p, 0);
		while (!(b % p)) fb.back().sec ++, b /= p;
	}
	int p = 0, q = 0;
	while (p < fa.size() && q < fb.size()) {
		int pr, cnt;
		if (fa[p].fir == fb[q].fir) {
			pr = fa[p].fir, cnt = fa[p].sec + fb[q].sec;
			p ++, q ++;
		} else if (fa[p].fir < fb[q].fir) {
			pr = fa[p].fir, cnt = fa[p].sec; p ++;
		} else {
			pr = fb[q].fir, cnt = fb[q].sec; q ++;
		}
		if (cnt > 1) vc.emplace_back(pr);
		for (auto pri : factor[pr - 1])
			vc.emplace_back(pri);
		phi /= pr, phi *= (pr - 1);
	}
	while (p < fa.size()) {
		int pr = fa[p].fir, cnt = fa[p].sec; p ++;
		if (cnt > 1) vc.emplace_back(pr);
		for (auto pri : factor[pr - 1])
			vc.emplace_back(pri);
		phi /= pr, phi *= (pr - 1);
	}
	while (q < fb.size()) {
		int pr = fb[q].fir, cnt = fb[q].sec; q ++;
		if (cnt > 1) vc.emplace_back(pr);
		for (auto pri : factor[pr - 1])
			vc.emplace_back(pri);
		phi /= pr, phi *= (pr - 1);
	}
	sort(vc.begin(), vc.end());
	vc.erase(unique(vc.begin(), vc.end()), vc.end());
	return {phi, vc};
}

int Solve(int N, int A, int B) {
	if (!A) return 1; if (A == 1) return __gcd(N, B);
	{
		int d = Gcd(N, A), g;
		if (d != 1) {
			int _N = N / d, _A = A % _N,
				_B = 1ll * Pow(A, N, N) * B % _N;
			return Solve(_N, _A, _B);
		}
	};
	int g = __gcd(A - 1, B), _A = (A - 1) / g, _N = N / Gcd(N, _A), ans = 0;
	auto [Phi, vc] = Get_Phi(N, _A);
	function<void(int, ll)> calc = [&](int n, ll C) {
		if (his.count(n)) return; his[n] = 1;
		ll mod = 1ll * N * _A / n;
		for (auto p : vc) while (!(C % p) && Pow(A, C / p, mod) <= 1) C /= p;
		ans += 1ll * N / _N * phi[_N / n] / C;
		for (auto p : factor[_N / n]) calc(n * p, C);
		return;
	};
	return his.clear(), calc(1, Phi), ans;
}

void slv() {
	n = Read<int>(), q = Read<int>(), Init();
	while (q --) {
		int a = Read<int>(), b = Read<int>();
		Write(Solve(n, a, b), '\n'), Flush();
	}
	return;
}
void clr() {
	
	return;
}

bool Med;
int main() {
#ifdef LOCAL
	freopen("!in.in", "r", stdin);
	freopen("!out.out", "w", stdout);
	fprintf(stderr, "%.3lf Mb\n", fabs((&Mbe - &Med) / 1048576.0));
#endif
	int T = 1;
//	int T = Read<int>();
	while (T --) slv(), clr();
	Flush();
#ifdef LOCAL
	fprintf(stderr, "%d ms\n", (int)clock());
#endif
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void FastIO::Write(T, char)’:
Main.cpp:56:17: warning: this ‘while’ clause does not guard... [-Wmisleading-indentation]
   56 |                 while (tp --) pc(stk[tp]); pc(c); return;
      |                 ^~~~~
Main.cpp:56:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘while’
   56 |                 while (tp --) pc(stk[tp]); pc(c); return;
      |                                            ^~
Main.cpp: In function ‘void FastIO::Write(char*)’:
Main.cpp:67:17: warning: this ‘while’ clause does not guard... [-Wmisleading-indentation]
   67 |                 while (*s != '\0') pc(*s), s ++; return;
      |                 ^~~~~
Main.cpp:67:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘while’
   67 |                 while (*s != '\0') pc(*s), s ++; return;
      |                                                  ^~~~~~
Main.cpp: In function ‘void Init()’:
Main.cpp:92:25: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   92 |                         if (1ll * i * j > n) break; vis[i * j] = true;
      |                         ^~
Main.cpp:92:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   92 |                         if (1ll * i * j > n) break; vis[i * j] = true;
      |                                                     ^~~
Main.cpp: In function ‘std::pair<long long int, std::vector<int> > Get_Phi(int, int)’:
Main.cpp:125:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  125 |         while (p < fa.size() && q < fb.size()) {
      |                ~~^~~~~~~~~~~
Main.cpp:125:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  125 |         while (p < fa.size() && q < fb.size()) {
      |                                 ~~^~~~~~~~~~~
Main.cpp:140:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  140 |         while (p < fa.size()) {
      |                ~~^~~~~~~~~~~
Main.cpp:147:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  147 |         while (q < fb.size()) {
      |                ~~^~~~~~~~~~~
Main.cpp: In function ‘int Solve(int, int, int)’:
Main.cpp:160:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  160 |         if (!A) return 1; if (A == 1) return __gcd(N, B);
      |         ^~
Main.cpp:160:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  160 |         if (!A) return 1; if (A == 1) return __gcd(N, B);
      |                           ^~
Main.cpp:162:36: warning: unused variable ‘g’ [-Wunused-variable]
  162 |                 int d = Gcd(N, A), g;
      |                                    ^
Main.cpp: In lambda function:
Main.cpp:172:17: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  172 |                 if (his.count(n)) return; his[n] = 1;
      |                 ^~
Main.cpp:172:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  172 |                 if (his.count(n)) return; his[n] = 1;
      |                                           ^~~

Judge Result