Problem 51

素数数字替换

将两位数*3的第一个数字代换为任意数字,在九个可能值中有六个是素数:13、23、43、53、73和83。

将五位数56**3的第三和第四位数字代换为相同的任意数字,就得到了十个可能值中有七个是素数的最小例子,这个素数族是:56003、56113、56333、56443、56663、56773和56993。56003作为这一族中最小的成员,也是最小的满足这个性质的素数。

通过将部分数字(不一定相邻)代换为相同的任意数字,有时能够得到八个素数,求满足这一性质的最小素数。


爆搜剪枝即可。加上一些小小的猜测。

code

#include<bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
int lim=8;
int d[]={1,3,7};
const int N=1000010;
int st[N],pr[N],cnt;
void prime(int n=N-10){
    for(int i=2;i<=n;i++){
        if(!st[i])st[i]=2,pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
    puts("done");
}
inline void dfs(reg int k,reg int unknow,reg int know,reg int rest){
    if(k-1<rest)return;
    if(k==1){

        int f,ans;
        for(int v=0;v<3;v++){
            f=0,ans=0;
            for(int i=0;i<=9;i++){
                int tmp=(unknow*i+know)*10+d[v];
                if(tmp>N||st[tmp]!=2)continue;
                ans++;
                if(!f)f=tmp;
                else if((f<<3)+(f<<1)<tmp)return;
                if(ans+(9-i)<lim)break;
            }

            if(ans==lim){
                printf("%lld\n",f);
                exit(0);
//                return;
            }
        }
        return;
    }
    for(int i=0;i<=9;i++)
        dfs(k-1,unknow*10,know*10+i,rest);
    dfs(k-1,unknow*10+1,know*10,rest-1);
    return;
}
signed main(){
    prime();
    for(int k=4;;k++)
        for(int l=3;l<k;l+=3)
            dfs(k,0,0,l);
    return 0;
}


Problem 52

重排的倍数

可以看出,125874和它的两倍251748拥有同样的数字,只是排列顺序不同。

有些正整数x满足2x、3x、4x、5x和6x都拥有相同的数字,求其中最小的正整数。


暴力枚举六位数就完了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int to(int x){
    int f=0;
    while(x){
        f+=pow(10,x%10);
        x/=10;
    }
    return f;
}
int a[7];
signed main(){
    for(int i=100000;i<=166667;i++){
        int f=1;
        for(int p=1;p<=6&&f;p++){
            a[p]=to(i*p);
            if(p>1&&a[p]!=a[p-1])f=0;
        }
        if(f){
            printf("%lld\n",i);
//            break;
        }
    }
    return 0;
}


Problem 53

组合数选择

从五个数12345中选择三个恰好有十种方式,分别是:

123、124、125、134、135、145、234、235、245和345

在组合数学中,我们记作:$\displaystyle \binom 5 3 = 10 = 10$。

一般来说,$\displaystyle \binom n r = \dfrac{n!}{r!(n-r)!}$,其中r ≤ n,n! = n×(n−1)×…×3×2×1,且0! = 1。

直到n = 23时,才出现了超出一百万的组合数:$\displaystyle \binom {23} {10} = 1144066$。

若数值相等形式不同也视为不同,对于1 ≤ n ≤ 100,有多少个组合数$\displaystyle \binom n r$超过一百万?


$C^r_n=C^{n-r}_n=\frac{n!}{r!(n-r)!}$

$C_n^{r+1}=\frac{n!}{(r+1)!(n-r-1)!}=C^r_n*\frac{n-r}{r+1}$

于是就可以愉快地递推求组合数了,反正不超过一百万就行。

如果超过了一百万,那么需要计算一下有多少个大于一百万的。

在n不变,r递增时,$C_n^r$是先递增再递减的,所以我们稍微考虑一下奇偶性计算答案即可。


code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100;
const int MX=1e6;
int ans;
signed main(){
    for(int n=1;n<=N;n++){
        int res=n;
        for(int r=1;r<n;r++){
            res*=(n-r);
            res/=(r+1);
            if(res>MX){
                if(n&1)ans+=(((n>>1)-r)<<1)+1;
                else ans+=(((n>>1)-1-r)<<1); 
                break;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Problem 54

扑克手牌

在扑克游戏中,玩家的手牌由五张牌组成,其等级由低到高分别为:

  • 单牌:牌面最大的一张牌。
  • 对子:两张牌面一样的牌。
  • 两对:两个不同的对子。
  • 三条:三张牌面一样的牌。
  • 顺子:五张牌的牌面是连续的。
  • 同花:五张牌是同一花色。
  • 葫芦:三条带一个对子。
  • 四条:四张牌面一样的牌。
  • 同花顺:五张牌的牌面是连续的且为同一花色。
  • 同花大顺:同一花色的10、J、Q、K、A。

牌面由小到大的顺序是:2、3、4、5、6、7、8、9、10、J、Q、K、A。

如果两名玩家的手牌处于同一等级,那么牌面较大的一方获胜;例如,一对8胜过一对5(参见例1);如果牌面相同,例如双方各有一对Q,那么就比较玩家剩余的牌中最大的牌(参见例4);如果最大的牌相同,则比较次大的牌,依此类推。

考虑以下五局游戏中双方的手牌:

| 手牌 | 玩家1 | 玩家2 | 胜者 |
| :-: | :-: | :-: | :-: |
| 1 | 红桃5 草花5 黑桃6 黑桃7 方片K | 草花2 黑桃3 黑桃8 方片8 方片10 | 玩家2 |
| | 一对5 | 一对8 | |
| 2 | 方片5 草花8 黑桃9 黑桃J 草花A | 草花2 草花5 方片7 黑桃8 红桃Q | 玩家1 |
| | 单牌A | 单牌Q | |
| 3 | 方片2 草花9 黑桃A 红桃A 草花A | 方片3 方片6 方片7 方片10 方片Q | 玩家2 |
| | 三条A | 同花方片 | |
| 4 | 方片4 黑桃6 红桃9 红桃Q 草花Q | 方片3 方片6 红桃7 方片Q 黑桃Q | 玩家1 |
| | 一对Q | 一对Q | |
| | 最大单牌9 | 最大单牌7 | |
| 5 | 红桃2 方片2 草花4 方片4 黑桃4 | 草花3 方片3 黑桃3 黑桃9 方片9 | 玩家1 |
| | 葫芦 | 葫芦 | |
| | (三条4) | (三条3) | |

在这个文本文件poker.txt中,包含有两名玩家一千局的手牌。每一行包含有10张牌(均用一个空格隔开):前5张牌属于玩家1,后5张牌属于玩家2。你可以假定所有的手牌都是有效的(没有无效的字符或是重复的牌),每个玩家的手牌不一定按顺序排列,且每一局都有确定的赢家。

其中有多少局玩家1获胜?


注意10在数据中用字符'T'表示。

目前为止遇到码量最大的一道题了,主要说一下坑点。其实也不算太坑

首先是最大的牌比较不出答案就比较次大的,并且是保证有输赢的。

这就让我们必须对每一副牌找到一个最优的方案让它能打出尽可能大的牌。

还有就是,比较了这副牌之后,实质是已经打出去了,更低等级的牌型也不能再用比较过的牌了。

这就是让我调了很久没调出来的问题。

思路是用优先队列从大到小存下每个牌型的牌,比如5张的同花就把数值排序后从大到小压入优先队列,让它自己比较。比如同花2,5,6,7,10,压进去的就是1007060502,这样可以保证从大到小比较每张牌。

如果遇到了三条,需要从对子里面剔除之前放进去的,同理,四条要把三条和对子都清空,两对要清空对子,葫芦也要清空对子和三条。

理解了这些代码就比较容易实现了,还是放一下有点丑的代码(指全是tmp)

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
priority_queue<int> q[20],Q[20];
int cur[30],num[30];
string a[10];
map<char,int> to;
int calc(){
    memset(cur,0,sizeof cur);
    memset(num,0,sizeof num);
    for(int i=9;i>=1;i--){
        while(q[i].size()){
            q[i].pop();
        }
    }
    int same_cur=0;
    int get_num[6];
    for(int i=1;i<=5;i++){
        cin>>a[i];
        int Num=to[a[i][0]],Cur=a[i][1]-'A';
        get_num[i]=Num;
        num[Num]++;
        q[1].push(Num);
        if(num[Num]==2)q[2].push(Num);
        if(num[Num]==3){
            queue<int> tmp;
            while(q[2].top()!=Num){
                tmp.push(q[2].top());
                q[2].pop();
            }
            q[2].pop();
            while(tmp.size())q[2].push(tmp.front());
            q[4].push(Num);
        }
        if(num[Num]==4){
            q[8].push(Num);
            while(q[2].size())q[2].pop();
            while(q[4].size())q[4].pop();
        }
        cur[Cur]++;
        if(cur[Cur]==5)same_cur=1;
    }
    if(q[2].size()==1&&q[4].size()==1){
        q[7].push(q[4].top()*100+q[2].top());
        q[4].pop(),q[2].pop();
    }
    if(q[2].size()==2){
        int tmp=q[2].top();
        q[2].pop();
        q[3].push(100*max(tmp,q[2].top())+min(tmp,q[2].top()));
        q[2].pop();
    }
    for(int i=14;i>=6;i--){
        if(num[i]&&num[i-1]&&num[i-2]&&num[i-3]&&num[i-4]){
            if(same_cur)q[9].push(i);
            else q[5].push(i);
        }
    }
    sort(get_num+1,get_num+6);
    if(same_cur&&q[9].empty())
        q[6].push(get_num[5]*100000000+get_num[4]*1000000+get_num[3]*10000+get_num[2]*100+get_num[1]);

//    for(int i=9;i>=1;i--){
//        printf("Level: %d\n",i);
//        while(q[i].size()){
//            printf("%d ",q[i].top());
//            q[i].pop();
//        }
//        puts("done");
//    }
}
signed main(){
    freopen("game.txt","r",stdin);
    to['2']=2,to['3']=3,to['4']=4,to['5']=5;
    to['6']=6,to['7']=7,to['8']=8,to['9']=9;
    to['T']=10,to['J']=11,to['Q']=12,to['K']=13,to['A']=14;
    int ans=0;
    for(int i=1;i<=1000;i++){
        printf("game %d : ",i);
        calc();
        for(int i=9;i>=1;i--)
            Q[i]=q[i];
        calc();
        int f=0;
        for(int i=9;i>=1&&!f;i--){
            if(Q[i].empty()&&q[i].empty())continue;
            while((!Q[i].empty())&&(!q[i].empty())){
                if(Q[i].top()==q[i].top()){
                    Q[i].pop(),q[i].pop();
                    continue;
                }
                puts(Q[i].top()>q[i].top()?"win":"lose");
                ans+=(Q[i].top()>q[i].top());
                f=1;
                break;
            }
            if(!f&&q[i].size()+Q[i].size()){
                puts(Q[i].size()?"win":"lose");
                ans+=(Q[i].size()!=0);
                f=1;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


Problem 55

利克瑞尔数

将47倒序并相加得到47 + 74 = 121,是一个回文数。

不是所有的数都能像这样迅速地变成回文数。例如,

349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337

也就是说,349需要迭代三次才能变成回文数。

尽管尚未被证实,但有些数,例如196,被认为永远不可能变成回文数。如果一个数永远不可能通过倒序并相加变成回文数,就被称为利克瑞尔数。出于理论的限制和问题的要求,在未被证否之前,我们姑且就认为这些数确实是利克瑞尔数。除此之外,已知对于任意一个小于一万的数,它要么在迭代50次以内变成回文数,要么就是没有人能够利用现今所有的计算能力将其迭代变成回文数。事实上,10677是第一个需要超过50次迭代变成回文数的数,这个回文数是
4668731596684224866951378664(53次迭代,28位数)。

令人惊讶的是,有些回文数本身也是利克瑞尔数数;第一个例子是4994。

小于一万的数中有多少利克瑞尔数?

注意:2007年4月24日,题目略作修改,以强调目前利克瑞尔数理论的限制。


就硬模拟就好了,每次暴力翻转相加判回文。可以看下代码里判回文的技巧qaq。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int pow_[18];
int len(int x){
    int l=0;
    while(x)l++,x/=10;
    return l;
}
int get(int x){
    int l=len(x);
    int y=0;
    for(int i=0;i<l;i++){
        y+=pow_[l-i-1]*(x%10);
        x/=10;
    }
    return y;
}
inline bool hw(int x)
{
    int res=0;
    while(x>res)
        res=(res<<3)+(res<<1)+x%10,x/=10;
    return (x==res||x==res/10);
}
bool check(int x){
    for(int i=1;i<=50;i++){
        int y=get(x);
        x+=y;
        if(hw(x))return 0;
    }
    return 1;
}
signed main(){
    pow_[0]=1;
    for(int i=1;i<=17;i++)
        pow_[i]=pow_[i-1]*10;
    int ans=0;
    for(int i=1;i<=10000;i++){
        if(check(i))ans++;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 56

幂的数字和

一古戈尔($10^{100}$)是一个巨大的数字:一后面跟着一百个零。$100^{100}$则更是无法想像地巨大:一后面跟着两百个零。然而,尽管这两个数如此巨大,各位数字和却都只有1。

若a, b < 100,所有能表示为$a^b$的自然数中,最大的各位数字和是多少?


不想动脑子,干脆就高精度踩过去了。

code

#include<bits/stdc++.h>
using namespace std;
int a[250];
int main(){
    int ans=-1;
    for(int x=1;x<100;x++){
        for(int i=200;i>=1;i--)
            a[i]=0;
        a[1]=1;
        for(int y=1;y<100;y++){
            int res=0;
            for(int i=1;i<=200;i++)
                a[i]*=x;
            for(int i=1;i<=200;i++)
                a[i+1]+=a[i]/10,a[i]%=10,res+=a[i];
            res+=a[200];
            ans=max(ans,res);
        }
    }
    printf("%d\n",ans);
    return 0;
}


Problem 57

平方根逼近
2的平方根可以用一个无限连分数表示:

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...将连分数计算取前四次迭代展开式分别是:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

接下来的三个迭代展开式分别是99/70、239/169和577/408,但是直到第八个迭代展开式1393/985,分子的位数第一次超过分母的位数。

在前一千个迭代展开式中,有多少个分数分子的位数多于分母的位数?


找到规律再稍微控控精度就可以了。

code

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long fz=3,fm=2,ans=0;
    for(int i=2;i<=1000;i++){
        fz+=fm;
        swap(fz,fm);
        fz+=fm;
        if((int)log10(fz)>(int)log10(fm))ans++;
        if(fz>1e15)fz/=1000,fm/=1000;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 58

螺旋素数
从1开始逆时针螺旋着摆放自然数,我们可以构造出一个边长为7的螺旋数阵。

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 05 04 03 12 29
40 19 06 01 02 11 28
41 20 07 08 09 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

可以发现,所有的奇数平方都在这个螺旋方针的右下对角线上,更有趣的是,在所有对角线上一共有8个素数,比例达到8/13 ≈ 62%。

在这个方阵外面完整地再加上一层,就能构造出一个边长为9的螺旋方阵。如果不断重复这个过程,当对角线上素数的比例第一次低于10%时,螺旋数阵的边长是多少?


找规律判质数,线性筛会炸。

code

#include<bits/stdc++.h>
using namespace std;
int check(int num)
{
    if(num==1)return 0;
    if(num==2||num==3)return 1;
    if(num%6!=1&&num%6!=5)return 0;
    int tmp=sqrt(num);
    for(int i=5;i<=tmp;i+=6)
        if(num%i==0||num%(i+2)==0)
            return 0;
    return 1;
}
int main(){
    int now=1,del=0,ans=1,num=0;
    while(1){
        ans+=2;
        del+=2;
        for(int i=1;i<=4;i++){
            now+=del;
            num+=check(now);
        }
        if(1.0*num/(double)(1+ans/2*4)<0.1){
            printf("%d\n",ans);
            break;
        }
    }
    return 0;
}


Problem 59

异或解密

计算机上的每个字符都被指定了一个独特的代码,其中被广泛使用的一种是ASCII码(美国信息交换标准代码)。例如,大写字母A = 65,星号(*) = 42,小写字母k = 107。

一种现代加密方法是将一个文本文档中的符号先转化为ASCII码,然后将每个字节异或一个根据密钥确定的值。使用异或进行加密的好处在于,只需对密文使用相同的密钥再加密一次就能得到明文,例如,65 XOR 42 = 107,而107 XOR 42 = 65。

为了使加密难以破解,密钥要和明文一样长,由随机的字节构成。用户会把加密过的信息和密钥放置在不同的地方,解密时二者缺一不可。

不幸的是,这种方法对大多数人来说并不实用,因此一个略有改进的方法是使用一个密码作为密钥。密码的长度很有可能比信息要短,这时候就循环重复使用这个密码进行加密。这种方法需要达到一种平衡,一方面密码要足够长才能保证安全,另一方面需要充分短以方便记忆。

你的破解任务要简单得多,因为密钥只由三个小写字母构成。文本文档cipher.txt(右击并选择“目标另存为……”)中包含了加密后的ASCII码,并且已知明文包含的一定是常见的英文单词,解密这条消息并求出原文的ASCII码之和。


题意就是给定一段ASCll码,已知是用三位小写字母循环异或加密的,求出原文的ASCll码值的和。

image.png

code

#include<bits/stdc++.h>
using namespace std;
int d[10010],n,to[10010];
int main(){
    freopen("E59.txt","r",stdin);
    while(~scanf("%d",&d[++n]));
    n--;
    int ans=0;
    for(int a='a';a<='z';a++){
        for(int b='a';b<='z';b++){
            for(int c='a';c<='z';c++){
                for(int i=1;i<=n;i+=3){
                    to[i]=d[i]^a;
                    to[i+1]=d[i+1]^b;
                    to[i+2]=d[i+2]^c;
                }
                for(int i=1;i<=n;i++){
                    if(to[i]==' '&&to[i+1]=='t'&&to[i+2]=='h'&&to[i+3]=='a'&&to[i+4]=='t'&&to[i+5]==' '){
                        for(int k=1;k<=n;k++){
                            ans+=to[k];
                            cout<<(char)to[k];
                        }
                        puts("\n");
                        break;
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

Problem 60

素数对的集合

  1. 7、109和673是非常特别的一组素数。任取其中的两个并且以任意顺序连接起来,其结果仍然是个素数。例如,选择7和109,我们得到7109和1097均为素数。这四个素数的和是792,这是满足这个性质的一组四个素数的最小和。

若有一组五个素数,任取其中的两个并且以任意顺序连接起来,其结果仍然是个素数,求这样一组素数的最小和。


直接暴力枚举即可。

code

#include<bits/stdc++.h>
#define int long long
#define len(x) ((int)log10(x)+1)
using namespace std;
const int N=10010;
int st[N],pr[N],cnt;
void prime(int n=N-10){
    for(int i=2;i<=n;i++){
        if(!st[i])st[i]=2,pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int check_pr(int num)
{
    if(num<=N-10)return st[num]==2;
    if(num==1)return 0;
    if(num==2||num==3)return 1;
    if(num%6!=1&&num%6!=5)return 0;
    int tmp=sqrt(num);
    for(int i=5;i<=tmp;i+=6)
        if(num%i==0||num%(i+2)==0)
            return 0;
    return 1;
}
int p[15];
bool check(int a,int b){
    return check_pr(a*p[len(b)]+b)&&check_pr(b*p[len(a)]+a);
}
signed main(){
    p[0]=1;
    for(int i=1;i<=14;i++)
        p[i]=p[i-1]*10;
    prime();
    printf("%d\n",cnt);
    for(int i=5;i<=cnt;i++){
        int a=pr[i]%3;
        for(int j=i+1;j<=cnt;j++){
            if(pr[j]%3!=a||!check(pr[i],pr[j]))continue;
            for(int k=j+1;k<=cnt;k++){
                if(pr[k]%3!=a||!check(pr[i],pr[k])||!check(pr[j],pr[k]))continue;
                for(int l=k+1;l<=cnt;l++){
                    if(pr[l]%3!=a||!check(pr[i],pr[l])||!check(pr[j],pr[l])||!check(pr[k],pr[l]))continue;
                    for(int p=l+1;p<=cnt;p++){
                        if(pr[p]%3!=a||!check(pr[i],pr[p])||!check(pr[j],pr[p])||!check(pr[p],pr[k])||!check(pr[p],pr[l]))continue;
                        printf("%d %d %d %d %d %d\n",pr[i],pr[j],pr[k],pr[l],pr[p],pr[i]+pr[j]+pr[k]+pr[l]+pr[p]);
                    }
                }
            }
        }
    }
    return 0;
}


Problem 61

循环的多边形数

三角形数、正方形数、五边形数、六边形数、七边形数和八边形数统称为多边形数。它们分别由如下的公式给出:

| | | |
| - | - | - |
| 三角形数 | P3,n=n(n+1)/2 | 1, 3, 6, 10, 15, … |
| 正方形数 | P4,n=n2 | 1, 4, 9, 16, 25, … |
| 五边形数 | P5,n=n(3n−1)/2 | 1, 5, 12, 22, 35, … |
| 六边形数 | P6,n=n(2n−1) | 1, 6, 15, 28, 45, … |
| 七边形数 | P7,n=n(5n−3)/2 | 1, 7, 18, 34, 55, … |
| 八边形数 | P8,n=n(3n−2) | 1, 8, 21, 40, 65, … |

由三个4位数8128、2882、8281构成的有序集有如下三个有趣的性质。

  1. 这个集合是循环的,每个数的后两位是后一个数的前两位(最后一个数的后两位也是第一个数的前两位)。
  2. 每种多边形数——三角形数(P3,127=8128)、正方形数(P4,91=8281)和五边形数(P5,44=2882)——在其中各有一个代表。
  3. 这是唯一一个满足上述性质的4位数有序集。

存在唯一一个包含六个4位数的有序循环集,每种多边形数——三角形数、正方形数、五边形数、六边形数、七边形数和八边形数——在其中各有一个代表。求这个集合的元素和。


直接爆搜就好了,没什么技巧也没什么思维难度。

code

#include<bits/stdc++.h>
using namespace std;
inline int get(int n,int t){
    switch(t){
        case 3:return (n*(n+1)/2);
        case 4:return (n*n);
        case 5:return (n*(3*n-1)/2);
        case 6:return (n*(n*2-1));
        case 7:return (n*(n*5-3)/2);
        case 8:return (n*(3*n-2));
    }
}
int num[10][1010],top[10],used[10],Num[10];
vector<int> head[10][110];
int start_;
inline void dfs(int now,int dep,int sum){
    Num[dep]=now;
    if(dep==8){
        if(now%100==start_){
            printf("%d\n",sum);
            for(int i=3;i<=dep;i++)
                printf("%d ",Num[i]);
            puts("done");
            exit(0);
        }
        return;
    }
    int tmp=now%100;
    for(int add=3;add<=8;add++){
        if(used[add])continue;
        for(int i=0;i<head[add][tmp].size();i++){
            used[add]=1;
            dfs(head[add][tmp][i],dep+1,sum+head[add][tmp][i]);
            used[add]=0;
        }
    }
}
int main(){
    for(int i=1;i<=3000;i++){
        for(int t=3;t<=8;t++){
            int tmp=get(i,t);
            if(tmp>=1000&&tmp<=9999)num[t][++top[t]]=tmp;
        }
    }
    for(int p=3;p<=8;p++){
        for(int i=1;i<=top[p];i++){
            head[p][num[p][i]/100].push_back(num[p][i]);
        }
    }
    for(int type=3;type<=8;type++){
        for(int i=1;i<=top[type];i++){
            start_=num[type][i]/100;
            used[type]=1;
            dfs(num[type][i],3,num[type][i]);
            used[type]=0;
        }
    }
    return 0;
}


Problem 62

立方数重排

立方数41063625(345^3)可以重排为另外两个立方数:56623104(384^3)和66430125(405^3)。实际上,41063625是重排中恰好有三个立方数的最小立方数。

求重排中恰好有五个立方数的最小立方数。


暴力枚举找就完了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int to(int x){
    int a=0;
    while(x){
        a+=pow(10,x%10);
        x/=10;
    }
    return a;
}
map<int,int> t;
map<int,int> num;
signed main(){
    for(int i=1;i<=10000;i++){
        int p=pow(i,3);
        int x=to(p);
        if(!t[x])t[x]=p;
        num[x]++;
        if(num[x]==5){
            printf("%lld\n",t[x]);
        }
    }
    return 0;
}


Problem 63

幂次与位数

五位数16807=7^5同时也是一个五次幂。同样的,九位数134217728=8^9同时也是九次幂。

有多少个n位正整数同时也是n次幂?


5%的降智题,暴力就好了。

code

#include<bits/stdc++.h>
#define len(x) ((int)log10(x)+1)
using namespace std;
int main(){
    int ans=0;
    for(int a=1;a<=9;a++){
        for(int b=1;b<=25;b++){
            if(b==len(pow(a,b)))ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}


Problem 64

把每一步得到的值记录为$a+\frac{\sqrt n-x}{y}$,考虑怎么转换到下一步。

根据题意,下一步是$\frac{y}{\sqrt n-x}$,我们也要把这个值表示成上面的形式。

把新得到的三个数记录为$a',x',y'$,很明显,$a'=\lfloor \frac{y}{\sqrt n-x} \rfloor$。

然后,我们把这个分数给分母有理化,得到$\frac{y(\sqrt n+x)}{(\sqrt n-x)(\sqrt n+x)}=\frac{y(\sqrt n+x)}{n-x^2}$

故$y'=n-x^2$,问题就在于这个$x'$。

那么变成真分数后,现在的分子是$y(\sqrt n+x)-a'y'$,根据观察,$y'$和分子具有相同的因数$y$,所以约分即可。至于证明我当然是不会的,有空了丕定再看看。

所$y'=\frac{n-x^2}{y},x'=-x+a'y'$,然后注意到这可能出现负数,那么根据样例,此时的$x'=-x',a'=a'+\frac{2x'}{y'}$。

那么递推计算就好了。

code

#include<bits/stdc++.h>
#define sqr(x) ((int)sqrt(x))
using namespace std;
map<int,map<int,map<int,int> > > mp;
int main(){
    int ans=0;
    for(int n=2;n<=10000;n++){
        int a=sqr(n),x=a,y=1;
        double ra=sqrt(n);
        if((int)ra==ra)continue;
        mp.clear();
        mp[a][x][y]=1;
        for(int i=2;;i++){
            int Y=(n-x*x)/y;
            int A=y>(ra-1.0*x)?y/(ra-1.0*x):0;
            int X=-x+A*Y;
            if(X<0)X=-X,A+=(2*X)/Y;
            a=A,x=X,y=Y;
            if(!mp[a][x][y])mp[a][x][y]=i;
            else{
                ans+=((i-mp[a][x][y])&1);
                break;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


Problem 65

image.png

考虑模拟,发现$\frac{1}{a+\frac{fz}{fm}}=\frac{fm}{fm*a+fz}$,于是打出来发现输出了奇怪的负数。

然后就打高精度,就封装起来了一个不能处理负数的加法乘法高精度

code

#include<bits/stdc++.h>
using namespace std;
int p[110];
void init(){
    int k=0;
    p[1]=2;
    for(int i=2;i<=105;i+=3){
        p[i]=1;
        p[i+1]=(k+2);k+=2;
        p[i+2]=1;
    }
}
struct node{
    int a[1010],len;
    void csh(){len=1;memset(a,0,sizeof a);}
    int &operator [] (int x){return a[x];}
    int operator[] (int x)const{return a[x];}
    node operator * (const node &x){
        node s;s.csh();s.len=len+x.len+1;
        for(int i=1;i<=len;i++)
            for(int j=1;j<=x.len;j++)
                s[i+j-1]+=a[i]*x[j];
        for(int i=1;i<=s.len;i++)
            s[i+1]+=s[i]/10,s[i]%=10;
        while(!s[s.len])s.len--;
        return s; 
    }
    node operator * (const int &x){
        node s;s.csh();
        s.len=len+(int)log10(x)+1+1;
        for(int i=1;i<=s.len;i++){
            s[i]+=a[i]*x;
            s[i+1]+=s[i]/10,s[i]%=10;
        }
        while(!s[s.len])s.len--;
        return s;
    }
    node operator + (const node &x){
        node s;s.csh();s.len=max(len,x.len)+1;
        for(int i=1;i<=s.len;i++){
            s[i]+=a[i]+x[i];
            s[i+1]+=s[i]/10,s[i]%=10;
        }
        while(!s[s.len])s.len--;
        return s;
    }
    node operator + (const int &x){
        node s;memcpy(s.a,a,sizeof a);s.len=len;
        s[1]+=x;
        int i=0;
        while(s[++i]>=10){
            s[i+1]+=s[i]/10,s[i]%=10;
        }
        s.len=max(s.len,i);
        return s;
    }
    node operator = (const int &x){
        int i=0,tmp=x;len=0;
        while(tmp)a[++len]=tmp%10,tmp/=10;
    }
    node operator = (const node &x){
        memcpy(a,x.a,sizeof a);
        len=x.len;
    }
    void print(){
        for(int i=len;i>=1;i--)
            printf("%d",a[i]);
        puts("");
    }
    int sum(){
        int s=0;
        for(int i=1;i<=len;i++){
            s+=a[i];
        }
        return s;
    }
}fz,fm;
int main(){
    init();
    int n=100;
    fz=0,fm=1;
    for(int i=n;i>=2;i--){
        node nfm=fm*p[i]+fz;
        fz=fm,fm=nfm;
    }
    fz=fz+fm*2;
    fz.print();
    fm.print();
    printf("%d\n",fz.sum());
    return 0;
}


E66

二次丢番图方程,要用到连分数的性质+高精度。

暂时不会做。有空补。


E67

同E18,数字三角形。

最后修改:2020 年 11 月 09 日 02 : 40 PM