有趣的数学题 · [NOI2002]Savage/[Violet · 5]樱花

$\rm{[NOI2002]}$ Savage

链接:$\color{violet}{Link}$

$\rm{Sol}$

不算特别难…其实就是求方程$$C_{i}+P_{i}x \equiv C_j+P_jx ~(\bmod ~M)$$不存在一个解使得$x \leq min(L_i,L_j)$时,$M$的最小值。然后因为题目中的数据,假设我们令每个野人都只是绕着圈走而不重复经过对方的路径——即$M$的最大值,也不过是$100\times 106\times 100 = O(1e6)$的级别,于是考虑直接枚举$M$, 然后check。由于最多共有$15$个野人,且单次exgcd是$\log n $级别的,所以复杂度上限是$O (Mn^2 \log C_{max}) < \Omega(1e8)$级别的。如果不是精心构造数据的话,可以直接艹过去。

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

1
2
3
4
5
6
7
8
9
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$,应该不断取模$b/ \gcd(a,b)$

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

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

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

那么便有$a(x-x_0)+b(y-y_0)=0$
两边同时除以$gcd(a,b)$可得:
$\frac{a}{gcd(a,b)}(x-x_0)=-\frac{b}{gcd(a,b)}(y-y_0)$ $ \quad$ $(1)$

而因为

$(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$

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

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

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

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

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

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

心得:我退役吧嘤。

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 ; }
}

$\rm{[Violet~5]}$ 樱花

链接:$\color{violet}{Link}$

这是好久之前做的一道题,突然被我发现了。大概就是求方程$$\frac{1}{x}+\frac{1}{y} = \frac{1}{n!}\quad (n \leq 1e6)$$的解的组数。

$\rm{Sol}$

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

我们将柿子变个形:
$$
\frac{x+y}{xy} = \frac{1}{n!} \\
n!x + n!y = xy
$$
然后我就不会了,此题完结

然后有一步很妙的是两边同时$+(n!)^2$得到:
$$
(n!)^2 + n!(x+y) -n!(xy) = (n!)^2\\
(n!-x)(n!-y)=(n!)^2
$$
然后就会发现我们只需要找出$(n!)^2$的因子个数就好了…

好像我从来没有写过$\tau$的样子,既然这样我就顺便记一个算因子个数的公式吧(其实就是乘法原理啦)
$$
x = \prod p_ix^{a_i} \longleftrightarrow\tau(x) = \prod (a_i+1)
$$
其实就是为了水字数

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

$233$窝萌思考一个比较显然的问题,就是一定会有$y>n!$。那窝萌不妨设$y = n!+T$,那么带回到原式里面就会有$$\frac{1}{x} + \frac{1}{n!+T} = \frac{1}{n!}$$继而有$$x = \frac{n!^2}{T}+n!$$那么其实一共就有$\tau(n!^2)$个合法答案,所以我们转而求$n!^2$的约数数量。

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

窝萌考虑筛出所有的$1-n$素数来,然后对于一个素数而言,由于窝萌要判断的对象是$n!$,他有一个奇妙的性质就是$$n!=\prod \limits_{i=1}^{n}{i}$$那么也就是说我们只需要判断对于一个当前给定的素数$p$,在$1-n$的所有数里面,$p$作为因子出现了多少次即可。那么也就是这个式子:

$$
Ans = \prod \limits _{p \in prime }^{p \leq n}{\sum \limits _{i \geq 1}^{p^i \leq n}{\lfloor \frac{n}{p^i}} \rfloor +1}
$$

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

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 ;
}
-------------本文结束感谢您的阅读-------------