记录下Project Euler上的一些题。
Problem 59 : XOR decryption
暴力
枚举key的三个字母对密文进行解密。
猜测原文中空格字符应占最多，故可筛选出若干个文本，人工识别即可。
find_the_key：
#include <cstdio>
using namespace std;
int a[10000],k,maxspace;
char ch;
void decrypt(int i,int j,int q){
int temp=0;
for(int t=0;t<=k;){
if(++t<=k&&(a[t-1]^i)==' ')temp++;
if(++t<=k&&(a[t-1]^j)==' ')temp++;
if(++t<=k&&(a[t-1]^q)==' ')temp++;
}
if(temp>=maxspace){
maxspace=temp;
printf("========================================\n");
for(int t=0;t<=k;){
if(++t<=k)putchar(a[t-1]^i);
if(++t<=k)putchar(a[t-1]^j);
if(++t<=k)putchar(a[t-1]^q);
}
printf("\n");
}
}
int main(void){
freopen("p059_cipher.txt","r",stdin);
freopen("output.txt","w",stdout);
for(;~scanf("%d%c",&a[k],&ch);++k);
for(int i='a';i<='z';++i)
for(int j='a';j<='z';++j)
for(int q='a';q<='z';++q)
decrypt(i,j,q);
}get_answer:
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char a[]="(The Gospel of John, chapter 1) 1 In the beginning the Word already existed. He was with God, and he was God. 2 He was in the beginning with God. 3 He created everything there is. Nothing exists that he didn't make. 4 Life itself was in him, and this life gives light to everyone. 5 The light shines through the darkness, and the darkness can never extinguish it. 6 God sent John the Baptist 7 to tell everyone about the light so that everyone might believe because of his testimony. 8 John himself was not the light; he was only a witness to the light. 9 The one who is the true light, who gives light to everyone, was going to come into the world. 10 But although the world was made through him, the world didn't recognize him when he came. 11 Even in his own land and among his own people, he was not accepted. 12 But to all who believed him and accepted him, he gave the right to become children of God. 13 They are reborn! This is not a physical birth resulting from human passion or plan, this rebirth comes from God.14 So the Word became human and lived here on earth among us. He was full of unfailing love and faithfulness. And we have seen his glory, the glory of the only Son of the Father.";
int main(void){
int sum=0,len=strlen(a);
for(int i=0;i<len;++i)sum+=a[i];
printf("%d\n",sum);
}Problem 69 : Totient maximum
贪心
若$n=\prod_{i=0}^s p_i^{e_i}$是$n$的标准分解式，那么$\varphi (n)=n\prod_{i=0}^s (1-\frac{1}{p_i})$.于是$\frac{n}{\varphi (n)}=\frac{1}{\prod_{i=0}^s (1-\frac{1}{p_i})}$.
而$p_i$是递增的，故每次贪心取最小的$p_i$可以得到最优解，故$n$为满足$n=\prod_{i=0}^t p_i \leqslant 1000,000$的最大的$n$ 。
代码如下：
#include <iostream>
#define N 100005
using namespace std;
bool vis[N];
int p[N],k;
void prime(){
for(int i=2;i<=100000;++i){
if(!vis[i])p[k++]=i;
for(int j=0;j<k&&i*p[j]<=100000;++j){
vis[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
int main(void){
prime();
int ans=1;
for(int i=0;i<k&&ans*p[i]<=1000000;++i)ans*=p[i];
cout<<ans;
}Problem 71 : Ordered fractions
法里数列
$n$阶法里数列是$0$和$1$之间最简分数的数列，由小至大排列，每个分数的分母不大于$n$。
设$F_n$为$n$阶法里数列，则有如下性质：
- $|F_n|=|F_{n-1}|+\varphi (n)$.
因为$F_n$仅比$F_{n-1}$多了$E={\frac{p}{n}:(p,n)=1}$，其中$|E|=\varphi (n)$。由$|F_1|=2，$可推出$|F_n|=1+\sum_{i=1}^n \varphi(n)$.
- 若$\frac{a}{b}$和$\frac{c}{d}$是某$k$阶法里数列的相邻项，且$\frac{a}{b} < \frac{c}{d}$，则它们之差为$\frac{1}{bd}$，也就是说$bc-ad=1$。反之同样成立：若$\frac{a}{b}$，$\frac{c}{d}$均为真分数，且$\frac{a}{b} < \frac{c}{d}$，$bc-ad=1$，则有$\frac{a}{b}$和$\frac{c}{d}$在$k$阶法里数列中是邻项，$k=max{b,d}$.
- 若$\frac{a}{b}$和$\frac{c}{d}$是某$k$阶法里数列的相邻项，随着$k$增大，$\frac{a}{b}$和$\frac{c}{d}$间出现的第一项为$\frac{a+c}{b+d}$.
这里用到了法里数列的第三条性质。
代码如下：
#include <iostream>
using namespace std;
int main(void){
int a=2,b=5;
while(b+7<=1000000){
a+=3;
b+=7;
}
cout<<a;
}Problem 77 : Prime summations
二分+完全背包计数
设$n$的分解式的个数为$f(n)$，不难证明$f(n)$为单调函数，故若能较快求出$f(n)$则可用二分解.
直接分解求分解式的个数并不是很容易，考虑小于等于$n$的素数组合成$n$有多少种方案，于是问题就成了完全背包计数问题，求$f(n)$的复杂度为$O(\frac{n^2}{logn})$.
总复杂度为$O(n^2)$ 。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#define N 100005
using namespace std;
bool vis[N];
typedef long long ll;
ll p[N],k,dp[N];
void prime(){
for(ll i=2;i<N;++i){
if(!vis[i])p[k++]=i;
for(ll j=0;j<k&&p[j]*i<N;++j){
vis[p[j]*i]=1;
if(i%p[j]==0)break;
}
}
}
ll check(ll n){
memset(dp,0,sizeof(dp));dp[0]=1;
for(ll i=0;i<k&&p[i]<=n;++i)
for(ll j=p[i];j<=n;++j)
dp[j]+=dp[j-p[i]];
return dp[n];
}
int main(void){
prime();
ll l=1,r=500;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid)>5000)r=mid-1;
else l=mid+1;
}
cout<<l;
}Problem 79 : Passcode derivation
拓扑排序
将所有keylog（abc）按a->b->c建图（由文本文件可知不存在自环），进行拓扑排序。
注意到可能成环，故先枚举第一个数，测试得第一个数是7时，符合条件的字符串最短。
代码如下：
#include <vector>
#include <cstdio>
using namespace std;
int x,y,z,deg[10],k,idx,vis[10];
char ans[20];
vector<int>e[10];
int main(void){
freopen("p079_keylog.txt","r",stdin);
while(~scanf("%1d%1d%1d",&x,&y,&z)){
vis[x]=vis[y]=vis[z]=1;
deg[y]++;deg[z]++;
e[x].push_back(y);
e[y].push_back(z);
}
freopen("CON","r",stdin);
while(1){
for(idx=0;idx<10;++idx)
if(deg[idx]==0&&vis[idx])
break;
if(idx>=10)break;
ans[k++]=idx+'0';
for(int i=0;i<(int)e[idx].size();++i)
deg[e[idx][i]]--;
vis[idx]=0;
}
ans[k]='\0';
printf("%s\n",ans);
}Problem 122 : Efficient exponentiation
DFS
由快速幂的做法先确定$m(x)$的上界，直接DFS。
代码如下：
#include <cstdio>
using namespace std;
int a[201],path[15]={1},ans;
void init(){
for(int i=1;i<=200;++i){
int temp=i;
while(temp!=1){
if(temp&1)a[i]++;
temp>>=1;
a[i]++;
}
}
}
void dfs(int k){
if(path[k]>200||a[path[k]]<k)return;
if(a[path[k]]>k)a[path[k]]=k;
for(int i=0;i<=k;++i){
path[k+1]=path[k]+path[i];
dfs(k+1);
}
}
int main(void){
init();
dfs(0);
for(int i=1;i<=200;++i)ans+=a[i];
printf("%d\n",ans);
}Problem 123 : Prime square remainders
二项式定理
$$
\begin{eqnarray}
(p_n-1)^n+(p_n+1)^n \equiv (-1)^n+(-1)^{n-1}np+1+np(mod , p_n^2)\
\end{eqnarray}
$$
故$n$ 为奇数，化简得：
$$
\begin{eqnarray}
(p_n-1)^n+(p_n+1)^n \equiv 2np(mod , p_n^2)\
\end{eqnarray}
$$
接下来枚举一下就好了，复杂度$O(n)$ 。
代码如下：
#include <iostream>
using namespace std;
typedef long long ll;
ll n=3,prime[1000000],isprime[1000000]={1,1},k;
void init(ll n){
for(ll i=2;i<n;++i){
if(!isprime[i])prime[k++]=i;
for(ll j=0;j<k&&prime[j]*i<n;++j){
isprime[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main(void){
init(1000000);
while(n<1000000&&(2*n*prime[n-1]%(prime[n-1]*prime[n-1]))<=1e10)n+=2;
cout<<n;
}Problem 131 : Prime cube partnership
数论
$\because n^3+n^2p=n^2(n+p)=m^3$
$\therefore n^2$ 和$n+p$ 均为立方数时，上式成立
设$x^3=n+p,y^3=n$ ，
$\therefore p=x^3-y^3=(x-y)(x^2+xy+y^2)$
$\because p$ 是素数
$\therefore x-y=1$
接下来枚举$n$ 即可。
代码如下：
#include <iostream>
using namespace std;
typedef long long ll;
ll n=2,ans;
bool isprime(ll p){
if(p<2)return 0;
for(ll i=2;i*i<=p;++i)if(p%i==0)
return 0;
return 1;
}
ll cube(ll n){
return n*n*n;
}
int main(void){
while(cube(n)-cube(n-1)<1e6){
if(isprime(cube(n)-cube(n-1)))
ans++;
n++;
}
cout<<ans;
}Problem 182 : RSA encryption
数论
首先考虑对于一个确定的$e$ ，有多少个$x$ 满足$x^e \equiv x(mod , p)$ ，其中$p$ 为一个素数。
显然有两种情况：
- 当$x \equiv 0 (mod , p)$ 时，上述式子成立
- 当$x \not\equiv 0(mod , p)$ 时，上述式子等价于$x^{e-1} \equiv 1(mod , p)$
我们看第二种情况，因为$p$ 为素数，故一定存在原根$r$ ，令$x=r^t$ 。
上述式子可以表示为$r^{t(e-1)} \equiv 1(mod , p)$ 。
由原根的性质，可以得到$ord(r^{(e-1)})=\frac{\varphi(p)}{gcd(\varphi(p),e-1)}$ 。
故$t$ 在$N_p^*$ 中，有$\frac{\varphi(p)}{ord(r^{(e-1)})}=gcd(p-1,e-1)$ 种不同的取值。
综上所述，对于一个$e$ ，有$gcd(p-1,e-1)+1$ 个$x$ 满足$x^e\equiv x(mod , p)$ 。
接下来设$m \equiv x (mod , p) ,m \equiv y (mod , q), n=p \times q$ ，
则$m^eq \equiv mq (mod , n)$ ，$m^ep \equiv mp (mod , n)$ ，
所以$m^e(q-p) \equiv m(q-p) (mod , n)$ ，即$m^e \equiv m (mod , n)$ 。
由中国剩余定理可知，$m \equiv x (mod , p) ,m \equiv y (mod , q)$唯一确定一个$m \equiv qxq^{-1}+pyp^{-1} (mod , n)$ 。
故对于一个$e$ ，有$[gcd(p-1,e-1)+1]\times [gcd(q-1,e-1)+1]$ 个$m$ 满足$m^e \equiv m(mod ,n)$ 。
知道这个结论后，遍历一遍$e$ 即可得到答案，复杂度为$O(nlogn)$ 。
代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll inf=100000000000;
ll p=1009,q=3643,e[4000000];
ll n=q*p,f=(p-1)*(q-1),minx=inf,ans;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
ll Min(ll a,ll b){
return a<b?a:b;
}
int main(void){
for(int i=2;i<f;++i)if(gcd(i,f)==1){
e[i]=(gcd(i-1,p-1)+1)*(gcd(i-1,q-1)+1);
minx=Min(minx,e[i]);
}
for(int i=2;i<f;++i)if(e[i]==minx)
ans+=i;
cout<<ans<<"\n";
}Problem 250 : 250250
背包
预处理$1^1,2^2,3^3,…,250250^{250250}$ 模$250$ 后的值，做01背包即可。
代码如下：
#include <iostream>
using namespace std;
typedef long long ll;
const ll N=250250+5;
const ll p=250;
const ll q=1e16;
ll a[N],dp[N][250];
ll mul(ll a,ll b){return a*b%p;}
ll add(ll a,ll b){return (a+b)%p;}
ll powmod(ll a,ll n){
ll r=1;a%=p;
while(n){
if(n&1)r=mul(a,r);
a=mul(a,a);
n>>=1;
}
return r;
}
int main(void){
for(ll i=1;i<=250250;++i)
a[i]=powmod(i,i);
dp[0][0]=1;
for(ll i=1;i<=250250;++i){
for(int j=0;j<250;++j)if(dp[i-1][j]){
dp[i][add(j,a[i])]=(dp[i][add(j,a[i])]+dp[i-1][j])%q;
dp[i][j]=(dp[i][j]+dp[i-1][j])%q;
}
}
cout<<(dp[250250][0]-1+q)%q;
}Problem 531 : Chinese leftovers
数论
对于一个同余方程：
$$
\begin{cases}
x \equiv a_1(mod , n_1)\\
x \equiv a_2(mod , n_2)
\end{cases}\\
\begin{eqnarray}
&&\therefore x=a_1+k_1n_1=a_2+k_2n_2\\
&&\therefore a_1-a_2 \equiv k_2n_2(mod , n_1)
\end{eqnarray}
$$
设$g=gcd(n_1,n_2)$ ，可以得到若方程有解，则$g|(a_1-a_2)$ 必成立；其逆否命题成立。
$$
\begin{eqnarray}
&&\therefore \frac{a_1-a_2}{g} \equiv k_2 \frac{n_2}{g}(mod , \frac{n_1}{g})\\
&&\therefore k_2 \equiv \frac{a_1-a_2}{g} (\frac{n_2}{g})^{-1}(mod , \frac{n_1}{g})\\
&&\therefore k_2n_2 \equiv \frac{a_1-a_2}{g} (\frac{n_2}{g})^{-1}n_2(mod \frac{n_1n_2}{g})\\
&&\therefore x \equiv a_2+k_2n_2 \equiv a_2+\frac{a_1-a_2}{g} (\frac{n_2}{g})^{-1}n_2(mod \frac{n_1n_2}{g})
\end{eqnarray}
$$
复杂度$O(n^2logn)$ 。
代码如下：
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int prime[1005005],k,isprime[1005005]={1,1},phi[1005005]={0,1};
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll add(ll a,ll b,ll p){return (a+b)%p;}
ll mul(ll a,ll b,ll p){return (a*b)%p;}
ll powmod(ll a,ll n,ll p){
ll r=1;
while(n){
if(n&1)r=mul(r,a,p);
a=mul(a,a,p);
n>>=1;
}
return r;
}
ll inv(ll a,ll n){
return powmod(a,phi[n]-1,n);
}
void init(int n){
for(int i=2;i<=n;++i){
if(!isprime[i]){
phi[i]=i-1;
prime[k++]=i;
}
for(int j=0;j<k&&prime[j]*i<=n;++j){
isprime[prime[j]*i]=1;
if(i%prime[j]==0){
phi[prime[j]*i]=phi[i]*prime[j];
break;
}else phi[prime[j]*i]=phi[i]*(prime[j]-1);
}
}
}
ll solve(ll n,ll m){
if(phi[n]<phi[m])swap(n,m);
ll g=gcd(n,m),a1=phi[n],a2=phi[m];
if((a1-a2)%g)return 0;
ll k2=mul((a1-a2)/g%(n/g),inv(m/g,n/g),n/g);
return add(k2*m,a2,n*m/g);
}
int main(void){
init(1005000);
ll ans=0;
for(ll i=1000000;i<1005000;++i)
for(ll j=i+1;j<1005000;++j)
ans+=solve(i,j);
cout<<ans;
}