题目

1<= n <=50’000’000

求让 $2n^2-1$ 为质数的有多少

尝试

裸暴力

显然我们枚举n,然后每个计算到 $\sqrt{n}$, 时间复杂度$O(n^{1.5})$

在n取这么大,要大概一个小时, 显然不满足pe的期望1min

优化1

显然如果 $ 2n^2-1 = 0 (\bmod b)$

那么有 $ 2(b+n)^2-1 = 0 (\bmod b)$, 且这是充要的

这有两个好的性质,并不要求$2n^2-1$是质数或者合数

对于给定b总能找到一个小于b的n

看上去很美好,而实际操作上,也能降低一定的复杂度,不过这个方法空间要求很大,而上面的暴力是O(1)空间

其2每次进行筛的时候也不算快,也有不少重复筛的

优化2

我们存不下$2n^2-1$的质数,但是可以预运算$\sqrt{2n^2-1}$的质数 进行一定的提速

如何判断质数

Level 1

裸暴力,从2到开根

Level 2

众所周知 费马小定理$a^{p-1} = 1 (\bmod p), gcd(a,p) = 1$

当然这个表达式 p是质数一定成立,但是成立并不一定是质数

Level 3

尝试多个a的费马小定理,

依然是”概率”运气的判断,

依然可能表达式成立,但p不是质数

Level 4 Miller-Rabin

把费马小定理的$p-1$拆解成$p-1 = 2^k (2m+1), m\ge 0$

也就是 2幂次和奇数的乘积

如果p是质数,我们有 $2^{2^k(2m+1)} = 1 (\bmod p)$

也就是 $2^{2^{k-1}(2m+1)} = \pm 1 (\bmod p)$

如果 $2^{2^{k-1}(2m+1)} = 1 (\bmod p)$

那么 $2^{2^{k-2}(2m+1)} = \pm 1 (\bmod p)$

同样,我们可以尝试多个a

这样的话”运气”能好很多,本身还是概率的做法

Level 5

http://miller-rabin.appspot.com/

我们用别人的答案!

Jim Sinclair证明了如果a的取值把下面都测试一遍,那么在 $p<2^{64}$时,都是能判断质数的!

2, 325, 9375, 28178, 450775, 9780504, 1795265022

还是Miller-Rabin,不过我们使用了已有成果,(好奇是证明,还是暴力枚举,毕竟是2011-04-20的事情了

Level 6 AKS

上面要么慢,要么基于概率(或有限范围的历史答案)

$(x-a)^n = x^n-a (\bmod n), gcd(\forall a,n) = 1$,

n是质数时,根据2项式定理显然,

如果n 合数, $(X-a)^n - X^n-a $ 看成 $X$为变量, 其余部分为系数

那么 $X^i$的系数为$C(n,i) a^{n-i}$

把合数表示成其构成的质数相乘$n = p_1^m \cdots$, 那么2项式中$C(n,p_1) \neq 0 (\bmod p_1^m )$,因为$C(n,p_1) = \frac{n!}{p!(n-p)!}= \frac{(n-p+1)…(n)}{1…p}$ 分子只有n是p的倍数,分母只有p是n的倍数

所以$C(n,p_1)a^{n-p_1} \neq 0 (\bmod p_1^m)$ (因为a和n互质,不会包含因子$p_1$) 也说明 $C(n,p_1)a^{n-p_1} \neq 0 (\bmod n)$

注意我们$(X-a)^n - X^n-a $ 看成 $X$为变量, 其余部分为系数,后就是一个 f(X)的表达式, 有系数非零

例如 n = 4

$(x+a)^4 = x^4+C(4,1)ax^3+C(4,2)a^2x^2+C(4,3)a^3x+a^4 = x^4 + C(4,2)a^2x^2+a^4 (\bmod 4)$

$(x+a)^4 -(x^4+a) = 6a^2x^2+a^4-a (\bmod 4)$

想存在$x,gcd(a,4) = 1$,使得 $6a^2x^2+a^4-a \neq (\bmod 4)$, 我们的确能找到 a=1,x=1,有些地方说,

既然是关于x有系数的表达式,或者项数差异,说明它在模意义下非恒为零??? 这是模运算的什么定理吗

小证? 写成 系数乘上 x的从1取到n的范得Vandermonde 矩阵, 系数和结果都对n取mod,所以只能全是零才有解? 甚至如果希望陪结果,可以反向推?脑补证明的感觉可能有误. 比如如果要按mod算的话,那vandermonde矩阵的n列就全是0和部分 位置XD

但是要中间的系数全是n的倍数上面已经证明

有的地方说主要是等式而不是值?

TODO

其它

$(n-1)! = -1 (\bmod p)$ 当且仅当 p为质数,陶哲轩的书上也有这个

效率更差, 在一些特定场景有用

Code

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
#define rep(i,a,n) for (ll i=a;i<n;i++)

// overflow
ll quick_p(__int128_t b, ll p,const ll mod){
  __int128_t r = 1;
  while(p){
    if(p%2)(r*=b)%=mod;
    (b*=b)%=mod;
    p/=2;
  }
  return r%mod;
}

ll mr(ll base,ll v){
  if(base > v)return true;
  ll startp = v-1;
  while(startp%2 == 0)startp>>=1;
  ll p = startp;
  __int128_t r = quick_p(base,p,v);
  while(p != v-1){
    if(r == v-1)return true;
    if(r == 1)return p == startp;
    p*=2;
    // overflow
    (r*=r)%=v;
  }
  return false;
}

bool is_prime_64(ll v){
  if(v < 2)return false;
  if(v < 4)return true;
  // %6 = 1 or 5
  if((v % 6) % 4 != 1)return false;
  ll test_g[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  rep(i,0,7){
    if(!(mr(test_g[i],v)))return false;
  }
  return true;
}

bool isp(ll v){
  rep(i,2,v){
    if(i*i>v)return true;
    if(v%i == 0)return false;
  }
  return true;
}

int main(){
  ll ans = 0;
  rep(i,2,50'000'000+1){
    if(i % 500'000 == 0){
      printf("i:%lld\n",i);
    }
    ans += is_prime_64(2*i*i-1);
  }
  printf("ans:%lld\n",ans);
  return 0;
}

Ref

https://brilliant.org/wiki/prime-testing/

https://primes.utm.edu/prove/prove2_3.html

2002 primes is P

http://www.cs.tau.ac.il/~amnon/Classes/2019-Derandomization/Lectures/Lecture7-AKS-All.pdf

https://en.wikipedia.org/wiki/AKS_primality_test

系数与完整表达式的疑问也有人问过

http://blog.sciencenet.cn/blog-3224443-1115018.html

题目

每次新增一个塑料袋

可以把偶数个之前的塑料袋放入这个新增的塑料袋

求n次后 的状态数

f(4)=5

f(8)=1385

求f(24680)%1020202009

打表

显然 OEIS A000111

DP(n^3)

dp[i][j] = 第i步,剩余j个袋子

dp[i][j] = dp[i-1][j-1+d] * c(j-1+d,d), d = 0..i-j, step = 2,(i-j)%2=0

试图优化,内部运算也没有摆脱O(n^3), n在2w 搞不了

DP(n^2)

f(n+1) =

0个放袋子n+1里c(n,0) * f(0) * f(n)

2个放袋子n+1里c(n,2) * f(2) * f(n-2) ,我们 不关心 这2个 和 这n-2个 内部的关系,而只关心谁在n+1袋子里,谁在袋子外,有了c(n,2), 于是 这2个和n-2互不干扰,各自的结构只与其内部相关,所以方案数也就是f(2)和f(n-2)

2k个放袋子n+1里c(n,2k) * f(2k) * f(n-2k) ,我们 不关心 这2k个 和 这n-2k个 内部的关系,而只关心谁在n+1袋子里,谁在袋子外,有了c(n,2k), 于是 这2k个和n-2k互不干扰,各自的结构只与其内部相关,所以方案数也就是f(2k)和f(n-2k)

f(n+1) = sum( c(n,2k) * f(2k) * f(n-2k) ), k = 0..floor(n/2)

令g(n) = f(n)/(n!), 其实上面dp我也用了这个技巧,但是还是有剩余的阶乘,无法简化到递推

g(n+1) * (n+1) = sum( g(2k) * g(n-2k)), k = 0..floor(n/2)

Ref

https://hiragn.hatenablog.com/entry/2020/12/01/031135

https://gist.github.com/hrgnz/10c4c3afb5a332c8ad3428327e6459c0#file-pe709a-nb

完美洗牌

AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBB

变为

ABABABABABABABABABABABABABABABABAB

次数

52张需要8次变回原型

需要8次的方案的张数和为412

问

需要60次的方案的张数和是多少

解

首先 估计已经到2的60次方左右的搜索范围,暴力不可取

递推

f(i,n) = (i%n)*2+int(i>=n)

然后我们分开写

f(i,n) = 2i (i < n)

f(i,n) = 2(i-n)+1 (i >= n)

变形

f(i,n) = 2i - (2n-1) (i >= n)

合并

f(i,n) = (2i)%(2n-1) 这里就很神奇了

相当于每个值的变化都是在乘2,又膜运算有合并性, 所以任何值a的k次后的值为 (a * 2^k) % (2n-1)

所以要所有都会到原位其实就是 任意 a, a = (a * 2^k) % (2n-1)

a取1,也是最大循环节

题目变成 $(2^60-1)%(2n-1) = 0$ 且 $(2^(<60)-1)%(2n-1) != 0$

质因数分解一下就好

总结

关键在 int(i>=n)的那个表达式转换成纯的模运算表达式,后面都好做了

题目

https://codeforces.com/problemset/problem/1521/D

评分2500

题意

给你树

每次拆一条边,连两个点

用最小操作次数让树的形状变成链状

求具体方案

样例1e4组,每个数节点小于1e5,所有节点数小于2e5

过程中没有限制一定要保持是树

题解

拆与合并互不干扰,也不会因为顺序干扰,

如果先拆完再合并,合并就很easy,因为拆分出的每个联通块一定是链状.

那问题是怎么拆分

要拆的节点明显是,连接数大于3,任取一个节点为根, 计算每个节点深度,深度从大到小,那么一条点要拆边,一定是和它父节点拆(贪心性质), O(n)

无代码

评价

这题最有意思的地方在于,不是正确方法需要很复杂的思路,而是你能想到许许多多不正确的看似时间内的做法,

比如我考虑过

1. 多点-多点优先斷,连小于2的点. 问题:可能成环, 也可能不是最小覆盖
2. 任选根,连leaf,断公共祖先,递归处理,也存在重复断和断得小于1的问题
3. 找不重叠的链,断了后连:

1
2
3

1-2-3-4-5
    |
6-7-8-9-0

问题 非主链,和存在非连接链, 难找断开位置.

4. +多点优先

1
2
3
4
5

  1      3
  |      |
  2------4
  |      |
5-6-7  8-9-0

问题: 多点成链, 2次更优,可能找到非最小

等等错误的思路干扰

第678910个满足$2^i$前3位是$123$的,求$i$

看了几个, 方案

截断15位/double(相当于截断)

log转换乘为加法，本质上还是精度和截断?

递增:196/289/485(=196+285)，还是要截断 (这三个还是容易得到, 但也可能更大的组合(485+196=681))

2**196=100433627766186892221372630771322662657637687111424552206336
2**289=994646472819573284310764496293641680200912301594695434880927953786318994025066751066112
2**485=99895953610111751404211111353381321783955140565279076827493022708011895642232499843849795298031743077114461795885011932654335221737225129801285632

所以, 或者有什么精度估计的方法?

感觉

都可能有精度问题，只是刚好得到正确答案过了?????

所以有更正确的方案吗?或者证明上面正确性的方案

这篇似乎在证 https://projecteuler.net/action=redirect;post_id=342800

log

文章还提到了 log与渐进分数，递增与渐进分数分母的关系

$1.23 x 10^k <= 2^i < 1.24x10^k$

$log_{10}{1.23} + k <= i \cdot log_{10}{2} < log_{10}{1.24} + k$

$93 \log_{10}2= 27.995789596750246 \equiv -0.00421040324975408 \pmod {1}$

$196 \log_{10}2= 59.001879150140304 \equiv 0.001879150140304 \pmod {1}$

$289 \log_{10}2= 86.99766874689055 \equiv -0.00233125310945 \pmod {1}$

$485 \log_{10}2= 145.99954789703085 \equiv -0.00045210296915 \pmod {1}$

首先在$1~485$内，只有$196,289,485$是小于$l = log_{10}{(123+1)} - log_{10}{123} = 0.003516573722837535$的

考虑一个合法的i，得到的 $i\cdot log_{10}{2} - log_{10}{1.23}$的小数部分x

$x \in [0，0.001637423582533535(= 0.003516573722837535-0.001879150140304)]$，那么+196 依然在区间中

$x \in [0.00233125310945, 0.003516573722837535]$，那么+289 依然在区间中

$x \in x \in [0.00045210296915, 0.003516573722837535]$，那么+485 依然在区间中

三个区间的并 刚好是整个区间

综上，我们证明了间隔只是这3个中的

精度

其实有了这个大于小于表达式，i的精度可以观察差值, 与 可信位数乘以乘法的比较

$i\cdot log_{10}{2} - log_{10}{1.23}$的小数部分, 到$[0,0.003516573722837535]$ 的两边界

与$i$ 乘上$log_{10}{2}$的不可信位数之间的关系