PTA刷题笔记(C语言) | 7-42 整除光棍 (20分)

落日映苍穹つ 2023-07-25 14:18 82阅读 0赞

开始刷题，感觉代码量和基础太渣了，导致数据结构不会，重头慢慢刷吧~
在这里插入图片描述

1、题目

在这里插入图片描述
输入样例：

31

输出样例：

3584229390681 15

2、代码

  1. #include<stdio.h>
  2. int main(){ 
  3.     int x;
  4.     scanf("%d",&x);
  5.     int cnt=0;
  6.     int a=0,c=0,d;
  7.     while(a<x){ 
  8.         a=a*10+1;
  9.         cnt++;
  10.     }
  11.     while(1){ 
  12.         printf("%d",a/x);
  13.         a%=x;
  14.         if(a==0) break;
  15.         a=a*10+1;
  16.         cnt++;
  17.     }
  18.     printf(" %d",cnt);
  20.     return 0;
  21. }

在这里插入图片描述

3、讨论

这个题很有意思的哈，本来以为就是个 “简单” 题，用循环不断乘10加1，果然有两个 test 超时了，然后，，，就没有然后了。

  1. #include<stdio.h>
  2. #include<math.h>
  3. int main(){ 
  4.     int x;
  5.     scanf("%d",&x);
  6.     int i;
  7.     int cnt=0;
  8.     long long int a=0,c=0,d;
  9.     while(1){ 
  10.         a=a*10+1;
  11.         cnt++;
  12.         c=a/x;
  13.         d=a%x;
  14.         if(d==0){ 
  15.             printf("%lld %d",c,cnt);
  16.             break;
  17.         }
  18.     }
  19. // printf("%lld %d",c,cnt);
  21.     return 0;
  22. }

在这里插入图片描述
上网一搜，发现了一个奇淫技巧，就是模拟除法的运行，即：
在这里插入图片描述
什么意思呢？

就是只先生成一部分光棍数，在例子里是111，然后进行除法，相当于是从最高位开始计算结果（手写除法运算的步骤），当余数不为0，就在余数末尾加1当除数（不是加法的加，而是拼凑的意思，即1“加”1，是11）。

妙啊！！！
在这里插入图片描述
在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，82人围观）

还没有评论，来说两句吧...

相关阅读

    相关 整除光棍 (20 分)

    整除光棍 (20 分) 这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除

    旧城等待，旧城等待，/ 0 赞/ 88 阅读