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

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

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

--------------------

# 1、题目 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]  
**输入样例：**

**输出样例：**

3584229390681 15

--------------------

# 2、代码 #

#include<stdio.h>
    int main(){ 
    	int x;
    	scanf("%d",&x);
    	int cnt=0;
    	int a=0,c=0,d;
    	while(a<x){ 
    		a=a*10+1;
    		cnt++;
    	}
    	while(1){ 
    		printf("%d",a/x);
    		a%=x;
    		if(a==0) break;
    		a=a*10+1;
    		cnt++;
    	}
    	printf(" %d",cnt);
    	
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]

# 3、讨论 #

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

#include<stdio.h>
    #include<math.h>
    int main(){ 
    	int x;
    	scanf("%d",&x);
    	int i;
    	int cnt=0;
    	long long int a=0,c=0,d;
    	while(1){ 
    		a=a*10+1;
    		cnt++;
    		c=a/x;
    		d=a%x;
    		if(d==0){ 
    			printf("%lld %d",c,cnt);
    			break;
    		}
    	}
    // printf("%lld %d",c,cnt);
    	
    	return 0;
    }

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

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

妙啊！！！  
![在这里插入图片描述][20200409230912373.jpg]  
![在这里插入图片描述][20200411094111348.jpg]

[20200411094322263.jpg]: /images/20230528/93d08b04f49d471da3d83c6a58599289.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230528/667b437d9ed24076b994facdf9643dcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230528/888d5e71688e47bfabea780815a0e6c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: /images/20230528/f364594ad44446628739153a732f7361.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: /images/20230528/d395573bc8304550bea9a566c9f16c21.png
[20200409230912373.jpg]: /images/20230528/a852ce49cc8147e0ab096b5ee77280da.png
[20200411094111348.jpg]: /images/20230528/7fdc521a7c914e7d91820b9d24da7ba2.png