【题解】有趣的数学题

两道小清新数学题,分别是 [NOI2002]Savage 和 [Violet · 5]樱花 。

[NOI2002] Savage

克里特岛以野人群居而著称。岛上有排列成环行的 $M$ 个山洞。这些山洞顺时针编号为 $1,2,\dots,M$。岛上住着 $n$ 个野人,一开始依次住在山洞 $C_1,C_2,\dots,C_n$ 中。以后每年,第 $i$ 个野人会沿顺时针向前走 $P_i$ 个洞住下来。每个野人i有一个寿命值 $L_i$,即生存的年数。

奇怪的是,虽然野人有很多,但没有任何两个野人在有生之年处在同一个山洞中,使得小岛一直保持和平与宁静,这让科学家们很是惊奇。他们想知道,至少有多少个山洞,才能维持岛上的和平呢?数据保证有解,$M$ 的值不大于 $10^6$。

数据范围:$1\le n\le 15$,$1\le C_i,P_i\le 100$,$0\le L_i\le 10^6$

不算特别难…其实就是求让对于任意一组关于 $(i,j)$ 方程

均不存在一个解使得

时,$M$ 的最小值。然后因为题目中的数据,$M\leq 10^6$ 于是考虑直接枚举 $M$, 然后 check。

由于最多共有 $15$ 个野人,且单次 exgcd 是 $\log n $ 级别的,所以复杂度上限是 $O (Mn^2 \log C_{\max}) < \Omega(10^8)$。如果不是精心构造数据的话,可以直接艹过去。

喜闻乐见的是……我的exgcd似乎一开始有问题?我一开始是这么写的:

1
2
3
4
5
6
7
8
9
10
inline bool check(){
for (i = 1 ; i <= N ; ++ i)
for(j = i + 1 ; j <= N ; ++ j){
int a = P[i] - P[j], b = M, x, y, w = C[j] - C[i] ;
int qwq = exgcd(x, y, a, b) ; if (w % qwq) continue ;
x = x * w / qwq ; while (x <= 0) x += M ;
if (x <= min(L[i], L[j])) return 0 ;
}
return 1 ;
}

然后觉得一点问题都没有,$40pts$ 之后愣了大半天。

而事实上这个地方$x$应该是一个特解,而不是最小解。换句话说我为了求出准确的 $x$,应该不断取模$\frac{b}{\gcd(a,b)}$。

为什么?至于为什么,一开始我也懵的很。直到我翻出来很久之前我的一篇题解:

_这是上面这个式子为什么可以这么做的证明:_

若有 $ax+by=c$ 且 $a_0x+b_0y=c$ 。

那么便有 $a(x-x_0)+b(y-y_0)=0$ 。

两边同时除以 $\gcd(a,b)$ 可得:

而因为

所以由 $(1)$ 可得$\frac{b}{\gcd(a,b)}$ 整除 $(x-x_0)$ 。

所以很显然有$\frac{b}{\gcd(a,b)}\times{t}={(x-x_0)},t \in \mathbb Z$ 。

那么就有对于任意一个 $x_i$,有

$ x_i=x_0+\frac{b}{\gcd(a,b)} \times{t} $

我特么…智商已经回退到上个世纪了吧 qaq,自闭了。

这就是我整理这道题的原因…还有,上面 $P_i-P_j$ 似乎需要取模并使其变成正的,因为好像我的 $exgcd$ 里面限制了$A>0$ 的缘故。

哦,对哈,如果 A 和 B 其中任意一个 $<0$ 都会出现对负数取模的情况…咱也不知道对负数取模会怎么样.jpg

心得:我退役吧嘤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int i, j, N, M, C[MAXN], P[MAXN], L[MAXN] ;

int exgcd(int &x, int &y, int A, int B){
if (!B) { x = 1, y = 0 ; return A ;}
int t = exgcd(y, x, B, A % B) ; y -= A / B * x ; return t ;
}
inline bool check(){
for (i = 1 ; i <= N ; ++ i)
for(j = i + 1 ; j <= N ; ++ j){
int a = (P[i] - P[j] + M) % M + M, b = M, x, y, w = C[j] - C[i], qwq = exgcd(x, y, a, b) ; if (w % qwq) continue ;
x = x * w / qwq ; x = (x % (M / qwq) + (M / qwq)) % (M / qwq) ; if (!x) x += (M / qwq) ; if (x <= min(L[i], L[j])) return 0 ;
}
return 1 ;
}
signed main(){
cin >> N ;
for (i = 1 ; i <= N ; ++ i)
scanf("%d%d%d", &C[i], &P[i], &L[i]), M = max(M, C[i]) ;
for ( M ; ; ++ M) if (check()) { cout << M << endl ; return 0 ; }
}

[Violet~5] 樱花

好久之前做的一道题,突然被我发现了。大概就是

求方程的解的组数。

不想思考系列问题,我这么懒还是退役吧。(sigh)

我们将柿子变个形:

然后我就不会了,此题完结

然后有一步很妙的是两边同时 $+(n!)^2$ 得到:

然后就会发现我们只需要找出 $(n!)^2$ 的因子个数就好了…

好像我从来没有写过求 $\tau(x)$的样子,既然这样我就顺便记一个算因子个数的公式吧(其实就是乘法原理啦)

其实就是为了水字数

$\rm upd ~on ~2019.6.13$ : 我发现自己似乎之前听过这个题的”另解”,以前自己整理过:

思考一个比较显然的问题,就是一定会有 $y>n!$。那窝萌不妨设 $y = n!+T$,带回到原式里面就会有

继而有

那么其实一共就有 $\tau(n!^2)$ 个合法答案,所以我们转而求 $n!^2$ 的约数数量。

但是显然的是我们并不可以直接求解,当然我不知道高精度之后会怎么样,估计 $n\log n$ 一下还是有可能过的。但是考虑到常数巨大,所以卡过 $10^6$ 基本上是痴人说梦。所以我们思考一种清新脱俗我根本想不出来的做法。

窝萌考虑筛出所有的 $1-n$ 素数来,然后对于一个素数而言,由于窝萌要判断的对象是 $n!$,他有一个奇妙的性质就是

那么也就是说我们只需要判断对于一个当前给定的素数 $p$,在 $1-n$ 的所有数里面,$p$ 作为因子出现了多少次即可。那么也就是这个式子:

我们每次遍历一遍,保证只加一次,譬如质数$3$,三的倍数的个数产生的贡献是一,三的平方的倍数产生的贡献是二,但是我们从前往后扫的话,每次就只要增长一个贡献即可(类似于去重操作$233$)

嗯,我算一下蛤,法 2 的复杂度大概是 $O(\frac{n}{\ln n}\times \log n)=O(n)$ 。

然后是法 1 的代码:

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
#include <cstdio>
#include <bitset>
#include <iostream>

#define ll long long
#define MAXN 10000100
#define Mod 1000000007

int Prime[MAXN] ;
std :: bitset <MAXN> vis ;
long long N, i, j, cnt, Ans, Cnt[MAXN] ;

void Ego(){
vis[1] = vis[0] = 1 ;
for (i = 2 ; i <= N ; ++ i){
if (!vis[i]) Prime[++ cnt] = i ;
for (j = 1 ; j <= cnt ; ++ j){
if (i * Prime[j] > N) break ;
vis[i * Prime[j]] = 1 ;
if (!(i % Prime[j])) break ;
}
}
for (i = 1 ; i <= cnt ; ++ i)
for (j = Prime[i] ; j <= N ; j *= Prime[i])
( Cnt[i] += (N / j) ) %= Mod ;
}
int main(){
std :: cin >> N ; Ans = 1ll, Ego() ;
for (i = 1 ; i <= cnt ; ++ i)
(Ans *= (Cnt[i] << 1) + 1) %= Mod ;
std :: cout << Ans % Mod << std :: endl ; return 0 ;
}