Project Euler 做题记录

Project Euler 太好玩了。。。（雾

Problem 675

设 (omega(n)) 表示 (n) 的质因子个数，(S(n)=sum_{d|n}2^{omega(d)})，求 (F(n)=sum_{i=2}^nS(i!) mod (10^9+87))。

(n=10^7)

solution

$n=prod_{i=1}^kp_i^{e_i}$ $S(n)=prod_{i=1}^k(2e_i+1)$ 线性筛求出每个数的最小质因子之后就可以对 $10^7$ 以内的所有数质因数分解了。 时间复杂度 $O(sum_{i=1}^nomega(i))$

Problem 225

Tribonacci Number:(T_1=T_2=T_3=1)，(T_n=T_{n-1}+T_{n-2}+T_{n-3})。

求第 124 小的奇数 (k) 满足对任意正整数 (n)，(k ot|T_n)。

solution

答案很小，暴力即可。

Problem 137

设 Fibonacci 的生成函数为 (A_F(x))，若 (xin Q_+) 且 (A_F(x)in N_+)，则称 (A_F(x)) 为 Fibonacci golden nuggets。求第 15 小的这样的数。

[egin{aligned}A_F(x)&=frac{x}{1-x-x^2} \&=frac{frac{c}{d}}{1-frac{c}{d}-frac{c^2}{d^2}} \&=frac{cd}{c^2-cd+d^2}end{aligned} ]

若 ((c,d)=1)，因为 ((cd,c^2-cd+d^2)=(c,c^2-cd+d^2)(d,c^2-cd+d^2)=(c,d^2)(d,c^2)=1)，所以 (c^2-cd+d^2=1)。

结论：(x=frac{F_{2n+1}}{F_{2n}})时 (n=F_{2n+1}F_{2n})，其中 (F_n) 是 Fibonacci 数。

证明咕了。。

Problem 330

设

[a(n)=egin{cases}1&n<0\sumlimits_{i=1}^{+infty}frac{a(n-i)}{i!}&nge 0end{cases}=frac{A(n)e+B(n)}{n!} ]

其中 (A(n),B(n)in N)，求 ((A(10^9)+B(10^9)) mod 77777777)

---

设 (b(n)=a(n)-1)，则

[egin{aligned} b(n)&=sum_{ige 1}frac{b(n-i)+1}{i!}-1 \ &=sum_{ige 1}frac{b(n-i)}{i!}+e-2 end{aligned}]

设 (D(n)=frac{n!b(n)}{e-2})，则

[egin{aligned} D(n)&=sum_{ige 1}frac{D(n-i)n!}{i!(n-i)!}+n! \ &=n!+sum_{i=1}^ninom{n}{i}D(n-i) end{aligned} ]

所以 (a(n)=frac{(e-2)D(n)+n!}{n!})，所以 (A(n)=D(n),B(n)=n!-2D(n)).

把 (D(n)) 求出即可。

打表发现，(p) 为质数时，从第 (p) 项开始，(D(n)mod p)的循环节为 (p(p-1))，证明不会。。。

77777777 分解质因数之后使用中国剩余定理合并即可。

Problem 474

题目描述：求 (n!) 的因数中(mod k=m) 的数量。

数据范围：(n=10^6,k=10^5,m=65432)。

这题就是个暴力。

首先把 (le n) 的质数筛出来，把 (n!) 质因数分解，(p) 的指数 (sum_{ige 1} lfloorfrac{n}{p^i} floorle nsum_{ige 1}p^{-i}=frac{n}{p-1})。(f_{i,j})表示只看前 (i) 个质因数，(mod k=j) 的因数数量，直接转移是 (O(knloglog n))的。

这个也可以跑出来，但是会跑死你。

考虑优化，因为 (m) 中 (2) 的次数为 (3)，不含 (5) 质因子，且 (k=2^5*5^5)，所以只有 (8|j,16 ot|j,5 ot|j) 的 (j) 才是有用的。于是带上了一个 (frac{1}{20}) 的常数。可以在 1min 以内跑过去了。

Problem 608

题目描述：求 (sum_{d|m}sum_{k=1}^nsigma_0(dk))。

数据范围：(m=200!,n=10^{12})。

[egin{aligned} Ans&=sum_{d|m}sum_{k=1}^nsum_{x|d}sum_{y|k}[xot y] \ &=sum_{d|m}sum_{k=1}^nsum_{x|d}sum_{y|k}sum_{t|x,y} mu(t) \ &=sum_{t|m,tle n}mu(t)(sum_{t|y,y|k,kle n}1)(sum_{t|x,x|d,d|m}1) \ ext{Suppose} S(n)&=sum_{i=1}^nlfloorfrac{n}{i} floor\ T(prod_{i=1}^sp_i^{a_i})&=prod_{i=1}^sinom{a_i+2}{2}\ &=sum_{t|m,tle n}mu(t)S(lfloorfrac{n}{t} floor)T(frac{m}{t}) end{aligned} ]

code

```cpp #include #define Rint register int using namespace std; typedef long long LL; const int N = 203, mod = 1e9 + 7, step = 1e6; int m, pri[N], tot, alp[N], ans/*, cnt, cnt2*/; bool notp[N]; LL n; inline void upd(int &a, int b){a += b; if(a >= mod) a -= mod;} inline int sub(int a, int b){return (a < b) ? (a + mod - b) : (a - b);} inline void init(int n){ notp[0] = notp[1] = true; for(Rint i = 2;i <= n;++ i){ if(!notp[i]) pri[tot ++] = i; for(Rint j = 0;j < tot && i * pri[j] <= n;++ j){ notp[i * pri[j]] = true; if(!(i % pri[j])) break; } } } inline int calc(int n, int p){ int res = 0; n /= p; while(n){res += n; n /= p;} return res; } inline int S(LL n){ int res = 0; for(LL i = 1, j;i <= n;i = j){ j = n / (n / i) + 1; upd(res, (j - i) % mod * (n / i) % mod); } return res; } inline int SUM(int n){return (n * (n + 1ll) >> 1) % mod;} inline void dfs(LL now, int dep, int cf){ if(now > n) return; if(dep == tot){ upd(ans, (LL) S(n / now) * cf % mod); return; } dfs(now, dep + 1, (LL) cf * SUM(alp[dep] + 1) % mod); dfs(now * pri[dep], dep + 1, mod - (LL) cf * SUM(alp[dep]) % mod); } int main(){ scanf("%d%lld", &m, &n); init(m); for(Rint i = 0;i < tot;++ i) alp[i] = calc(m, pri[i]); dfs(1, 0, 1); printf("%d ", ans); } ```

Problem 362

题目描述：设 (f(n)) 表示把 (n) 分解为一些(ge 2) 的 Squarefree 的数的乘积的形式（无序）的方案数。求 (S(n)=sum_{i=1}^nf(i)).

数据范围：(n=10^{10}).

（当 (mu(n) ot= 0) 时 (n) 称为 Squarefree Number）

由于这个分解式要求无序，所以只能把 (le sqrt n) 的 Squarefree 的数求出来，设为 (k_0,k_1,ldots,k_{c-1})，设 (S(x,y)) 表示只用 (ge k_x) 的数分解 ([k_x,y]) 的数。则有

[S(x,y)=egin{cases}1+S(x+1,y)+S(x,lfloorfrac{y}{k_x} floor),&k_x^2le y \ sum_{i=1}^ymu(i)^2-x,&k_x^2>yend{cases} ]

第一个式子中：(k_x) 分解为 (k_x)，然后枚举是否含有 (k_x) 作为其中一个数。

第二个式子中，([k_x,y]) 中的 non-squarefree 的数是不能分解的，必定在之前就被考虑过，而 Squarefree 的不能再分解，所以就是这个式子了。

[sum_{i=1}^nmu(i)^2=sum_{i=1}^{lfloorsqrt n floor}mu(i)lfloorfrac{n}{i^2} floor ]

这东西就是个容斥，枚举 (i^2) 作为它的平方因子。直接 (O(sqrt n)) 做都可以。

顺便再把 (S) 和这个和式给记忆化一下。

时间复杂度并不知道，但是跑个十几秒就出来了。

code

```cpp #include #define Rint register int #define MP make_pair using namespace std; typedef long long LL; typedef pair pii; const int N = 111111; int m, pri[N], mu[N], tot, k[N], cnt; bool notp[N]; LL n; inline void init(int n){ notp[0] = notp[1] = true; mu[1] = 1; for(Rint i = 2;i <= n;++ i){ if(!notp[i]) mu[pri[tot ++] = i] = -1; for(Rint j = 0;j < tot && i * pri[j] <= n;++ j){ notp[i * pri[j]] = true; if(i % pri[j]) mu[i * pri[j]] = -mu[i]; else break; } if(mu[i]) k[cnt ++] = i; } } unordered_map g; inline LL calc(LL n){ if(g.count(n)) return g[n]; LL res = 0; for(LL i = 1;i * i <= n;++ i) res += n / i / i * mu[i]; return g[n] = res; } map M; inline LL dfs(int x, LL y){ pii p = MP(x, y); if(M.count(p)) return M[p]; if(x >= cnt || (LL) k[x] * k[x] > y) return calc(y) - x - 1; return M[p] = 1 + dfs(x + 1, y) + dfs(x, y / k[x]); } int main(){ scanf("%lld", &n); init(m = sqrt(n) + 1); printf("%lld ", dfs(0, n)); } ```

Problem 562

首先，我连毕克定理都忘了。

面积=内部点+边界点/2-1.

所以就是面积为 (frac{1}{2}) 的三角形。

要求周长最长，所以最长边的两个端点一定离原点比较远。设离原点距离平方 (ge 10^{14}-10^3). 然后用 exgcd 就可以解出第三个点了。

code 明天写。

Problem 490

题目描述：设 (f(n)) 表示长度为 (n) 的排列 (1=p_1,p_2,ldots,p_n=n) 满足 (|p_i-p_{i+1}|=3) 的个数。

求 (S(n)=sum_{i=1}^nf(i)^3 mod p)。

数据范围：(n=10^{14},p=10^9.)

---

pb 带我把这道题肝出来了。。。

设 (f_n,g_n,h_n) 表示在 (1,2,ldots,n) 的排列中，(1 ightarrow n,2 ightarrow n,3 ightarrow n) 的方案数。

把（推式子->写代码->测样例）不断重复，就可以获得以下的式子：

[egin{aligned} f_n&=f_{n-1}+g_{n-1}+h_{n-1} \ g_n&=f_{n-2}+g_{n-2}+f_{n-3}+f_{n-4}+g_{n-4}+h_{n-2}-f_{n-6} \ h_n&=2f_{n-3}+g_{n-3}+2f_{n-4}+f_{n-5}+h_{n-3}-f_{n-7}+g_{n-5} end{aligned} ]

然后化简：

[egin{aligned} f_n&=f_{n-1}+f_{n-4}+f_{n-5}+g_{n-1}+g_{n-2} \ g_n&=f_{n-1}+f_{n-3}+f_{n-4}-f_{n-6}+g_{n-4} \ end{aligned} ]

然而并不知道怎么去掉 (g_n)，所以硬上 BM.

[f_n=2f_{n-1}-f_{n-2}+2f_{n-3}+f_{n-4}+f_{n-5}-f_{n-7}-f_{n-8} ]

所以早就该写个状压

感觉三次方爆拆也是有线性递推式的，所以硬上BM。由于模数是 10^9，所以要求出不取模的值，所以用三个质数算之后使用CRT合并。

递推式系数

``` 7,3,110,657,2152,-3069,-52635,-261302,-153696,1473808,2397069,-311428,15762353,23085711,-47100311,129068460,562670682,851932061,925364934,1130031754,-4818794712,-13912313165,-20035999720,-27503231654,8949378103,10592790453,86984066471,-56538383977,310493682996,-555465996642,1018117858828,-492151027284,2597031578551,-4155106947436,4585759018316,-9918477547884,15345098186233,-16703435094128,14108978306373,-27430610896121,34471508084833,-41664710509024,56721748256014,-66444180626409,72030686017061,-36937223139909,37807899843246,-79005671659204,99579386233244,-91805685058556,53280640807504,-20165321105154,-47200378525336,98926314244247,-29644108051680,-98742930470195,92925853017229,91456358240235,-227581074843374,140985746410706,38693277606439,-71589702321590,-22128540237021,81893506257373,-49141821193336,-2978665835660,11325445924806,-16572398684339,37247712591350,-42178276310845,25148411068672,-8098925759012,1492489231468,-1796923760449,-262361213538,2822570675476,-2009433760337,933638513260,-1282209459128,1230923844512,-565730597095,31120448364,210053308828,-141425154588,43691863656,-81272454172,113172412506,-83602207124,59855112573,-45210437862,28195771570,-13763616116,6190641463,-4427241075,3051495474,-1495697702,760716994,-480886330,299865824,-128022945,40583768,-17920921,6498090,-2262358,2082694,-2003166,925167,-110850,4595,-3599,902,-2625,3642,-2359,285,-1,-7,-1,2,-1,1 ```

然后用矩阵做线性递推。

PS:答案有很多个7