题目

题目看起来好像很难的样子！其实不然，这是最简单的一道题。

算法

首先要注意的是：

\(number \cdot x + product \cdot y = 1\) ，那么我们称\(number\)与\(product\)不相冲。

等价于

当\(number\)和\(product\)互质时，那么我们称\(number\)与\(product\)不相冲。

所以求与\(product\)不冲突的\(number\)个数，即是求\(\varphi (product)\)(即\(product\)的欧拉函数)。

设\(product\)的质因数有\(p_1,p_2, \dotsb ,p_{cnt}\)

\(\varphi (product) = product \cdot \frac {p_1-1} {p_1} \cdot \frac {p_2-1} {p_2}\dotsb \frac {p_{cnt}-1} {p_{cnt}}\)

其中除法可以用逆元。

并且，题目保证\(product\)的质因数只有最小的\(60\)个质数，所以可以用线段数来维护\(product \mod 19961993\)的值以及\(product\)含有哪些质数。

代码

//#define debug

#ifdef debug

#define ep(...) fprintf(stderr, __VA_ARGS__);

#else

#define ep(...)

#endif 

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

const int n = 100000;

const int m = 60;

const int MOD = 19961993;

const int prime[60] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,

	73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,

	179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281};

struct Node

{

	int x;

	i64 set;

	Node ()

	{

	}

	Node (int _x, i64 _set) :

		x(_x), set(_set)

	{

	}

	Node operator + (const Node &o) const

	{

		return Node((i64) x * o.x % MOD, set | o.set);

	}

}T[262144];

#define idxl (idx << 1)

#define idxr (idx << 1 ^ 1)

Node Query(const int &idx, const int &L, const int &R, const int &x, const int &y)

{

	if (x <= L && y >= R) return T[idx];

	int M = (L + R) >> 1;

	if (y <= M) return Query(idxl, L, M, x, y);

	if (x > M) return Query(idxr, M + 1, R, x, y);

	return Query(idxl, L, M, x, y) + Query(idxr, M + 1, R, x, y);

}

void Modify(const int &idx, const int &L, const int &R, const int &x, const Node &newvalue)

{

	if (L == R) T[idx] = newvalue;

	else

	{

		int M = (L + R) >> 1;

		if (x <= M) Modify(idxl, L, M, x, newvalue);

		else Modify(idxr, M + 1, R, x, newvalue);

		T[idx] = T[idxl] + T[idxr];

	}

}

void Modify(const int &idx, const int &x)

{

	i64 set = 0;

	for (int i = 0; i < m; i ++)

	{

		if (x % prime[i] == 0)

		{

			set |= 1LL << i;

		}

	}

	Modify(1, 1, n, idx, Node(x, set));

}

int main()

{

#ifdef debug

	freopen("in", "r", stdin);

	freopen("out", "w", stdout);

#endif

	for (int i = 1; i <= n; i ++)

		Modify(i, 3);

	static int prime_rev[300];

	prime_rev[1] = 1;

	for (int i = 2; i < 300; i ++)

		prime_rev[i] = (i64) prime_rev[MOD % i] * (MOD - MOD / i) % MOD;

	int cases;

	scanf("%d", &cases);

	while (cases --)

	{

		int opt;

		scanf("%d", &opt);

		if (opt == 0)

		{

			int L, R;

			scanf("%d%d", &L, &R);

			Node res = Query(1, 1, n, L, R);

			ep("%lld\n", res.set);

			for (int i = 0; i < m; i ++)

			{

				if (res.set >> i & 1)

				{

					res.x = (i64) res.x * (prime[i] - 1) % MOD * prime_rev[prime[i]] % MOD;

				}

			}

			printf("%d\n", res.x);

		}

		else

		{

			int idx, x;

			scanf("%d%d", &idx, &x);

			Modify(idx, x);

		}

	}

	return 0;

}