U2yyy 2022-04-29 00:17 采纳率: 71.4%
浏览 81
已结题

光棍整除问题,debug过了,但是没过pta

题目如下:
这里所谓的“光棍”,并不是指单身汪啦~ 说的是全部由1组成的数字,比如1 11 111 1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如,111111就可以被13整除。 现在,你的程序要读入一个整数x,这个整数一定是奇数并且不以5结尾。然后,经过计算,输出两个数字:第一个数字s,表示x乘以s是一个光棍,第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。

提示:一个显然的办法是逐渐增加光棍的位数,直到可以整除x为止。但难点在于,s可能是个非常大的数 —— 比如,程序输入31,那么就输出3584229390681和15,因为31乘以3584229390681的结果是111111111111111,一共15个1。

输入格式:
输入在一行中给出一个不以5结尾的正奇数x(<1000)。

输出格式:
在一行中输出相应的最小的s和n,其间以1个空格分隔。

本题一开始没思路,后来知道了要模拟的是手工除法,就开始敲代码了,但是结果显示不对,我自己测试又好像没有问题,有没有dl来指一下错误

#include<stdio.h>
#include<windows.h>
void search(int x,int *cnt, int a[]);
int bytee(int number);
int main(){

int x,cnt;

int *p = &cnt;//声明一个p指向cnt,用来计算光棍个数

int a[cnt];//这里用了变量数组,编译器没报错,运行结果好像也没问题,但是我没有测试完,pta上面显示部分正确

scanf("%d",&x);

search(x,p,a);

int i,add = 0;

for(i=0;i<cnt;i++){
    add += a[i];
    //创建额add变量是判断a[i]前面是否为0的,如果为0就不输出,避免输出的数字前面带0
    if(add != 0){
        printf("%d",a[i]);
        //一个一个地输入存在数组里面的每一位数字
    }
}

printf(" %d",cnt);

system("pause");

return 0;

}

void search(int x,int *p,int a[]){
int i,s = 1;

*p = 0;

for( i=0; ; i++ ){
    a[i] = s/x;
    //存储每一位商的值
    int mid = s;
    //声明中间量存储s改变之前的值,因为要拿这个值来判断是否继续执行循环
    s = (s % x)*10+1;
    //这是每次的余数,因为是1111...,所以每次乘十再加一
    *p = *p + 1;
    //*p指向cnt,是用来计管滚数量的
    if(mid % x == 0){
       break;
    }
    //这个条件语句在mid刚好被x整除的时候退出循环
}

}

  • 写回答

1条回答 默认 最新

  • 对象被抛出 2022-04-29 08:17
    关注

    有个时间复杂度很低的思路. 假设这里x取13, 从ans=1开始, ans%x=1, 而(10ans+1)%x =( ((10(ans%x))%x)+1)%x, 只要不停地计算这个值, 看他什么时候等于0即可. 最大的的问题是不知道long long够不够用. 不够用的话得自己写大数模板写个%和*

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 5月27日
  • 已采纳回答 5月19日
  • 创建了问题 4月29日

悬赏问题

  • ¥15 救!ENVI5.6深度学习初始化模型报错怎么办?
  • ¥30 eclipse开启服务后,网页无法打开
  • ¥30 雷达辐射源信号参考模型
  • ¥15 html+css+js如何实现这样子的效果?
  • ¥15 STM32单片机自主设计
  • ¥15 如何在node.js中或者java中给wav格式的音频编码成sil格式呢
  • ¥15 不小心不正规的开发公司导致不给我们y码,
  • ¥15 我的代码无法在vc++中运行呀,错误很多
  • ¥50 求一个win系统下运行的可自动抓取arm64架构deb安装包和其依赖包的软件。
  • ¥60 fail to initialize keyboard hotkeys through kernel.0000000000