| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 700 人关注过本帖, 1 人收藏
标题:大大们。我又来了。。又是程序超时这让小白头疼的事
只看楼主 加入收藏
萝莉小纯情
Rank: 1
等 级:新手上路
帖 子:73
专家分:6
注 册:2012-12-8
结帖率:77.78%
收藏(1)
已结贴  问题点数:20 回复次数:17 
大大们。我又来了。。又是程序超时这让小白头疼的事
回文质数
时限:1000ms 内存限制:10000K  总时限:3000ms
描述:
因为151即是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。
写一个程序来找出范围[a,b](5 <= a < b <= 100000000)间的所有回文质数;
输入:单独一行,两个长整型数,a,b(以空格隔开)。
输出:
从小到大,输出一个回文质数的列表,一行一个。
输入样例:
5 500
输出样例:
5
7
11
101
131
151
181
191
313
353
373
383!

魔术数
时限:1000ms 内存限制:10000K  总时限:3000ms
描述:
给一个正整数k,1<k<10000,求一个最小的M,把M的第一位数移到最后面,让原来的数是后来的k倍。例如:K=4,102564:25641,102564=4*25641
输入:
第一行为数据的总个数N(N<100),以后N行分别是N个k值
输出:
对于每个k值,输出一个相应的M
程序马上给出哈
搜索更多相关主题的帖子: 内存 魔术 
2012-12-14 12:05
萝莉小纯情
Rank: 1
等 级:新手上路
帖 子:73
专家分:6
注 册:2012-12-8
收藏
得分:0 
#include<stdio.h>
int main()
{
int k,n,M,h,s,i,j,a,b;
scanf("%d",&n);
for (i =0;i<n;i++)
{
scanf ("%d",&k);
for (M=10;;M++)
{
j=1;
s=M;
while (s!=0)
{
s=s/10;
j*=10;
}
j=j/10;
a=M/j;
b=M%j;
h=b*10+a;
if (M==h*k)
{
printf("%d\n",M);
break;
}
}
}
}
魔术数
2012-12-14 12:06
萝莉小纯情
Rank: 1
等 级:新手上路
帖 子:73
专家分:6
注 册:2012-12-8
收藏
得分:0 
#include<math.h>
int main()
{
int a,i,z,m,n,j,b;
scanf("%d%d",&a,&b);
for( i=((a%2)>0?a:(a+1)); i<=b; i+=2)
{
j=0;
z=i;
if(z%2==0)
{
continue;
}
else
{
while (z!=0)
{
m=z%10;
j=j*10+m;
z=z/10;
}
}
if(j==i)
{
for (n=2;n*n<i;n++)
{
if(i%n==0)
{
break;
}
}
if (n*n>i)
{
printf ("%d\n",i);
}
}
}
}
回文质数
我觉得这两道有点类似。不过是不是除法太多了。。。穷举法。。
2012-12-14 12:11
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:10 
第一题构造法,分奇数位和偶数位讨论,比如5位,先枚举中间的那一位(0-9),先枚举前两位10-99,然后枚举第三位0-9,最后两位则由前两位得到,再判断是否是素数,偶数位类似

第二题有点不解,如果k>10,难道有一个数能移位后是之前数的10多倍吗?
2012-12-14 12:15
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
假如用1bit来表示是否是质数,那么100000000需要12M的内存,超过了10000K的限制
2的倍数肯定不是质数,那就可以将内存消耗降低一半,只要6M,这样就没超过限制
2012-12-14 12:15
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
回复 4楼 czz5242199
哦,懂了,次高位之类是0可以
2012-12-14 12:25
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
第二题
假设这个数是n位,最高位是a,其他位是b

则这个数是a*10^(n-1)+b,移动后是a+10b

a*10^(n-1)+b=k(a+10b)

(10^(n-1)-k)*a=(10k-1)*b

由于要求最小的,枚举n(2开始)

由于a/b=(10k-1)/(10^(n-1)-k)

利用欧几里得算法得到合适的a和b
2012-12-14 12:50
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
以下是引用czz5242199在2012-12-14 12:50:27的发言:

第二题

我也是这么想的,也这么写了,但对于k=11,在uint64_t范围内就没找到答案。不知道是本来就无解,还是选值范围太小
2012-12-14 13:02
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
这是我的代码
程序代码:
#include <stdio.h>

// a*10^b+c == (10*c+a)*k
// 则 c = a*(10^b-k)/(10*k-1)
unsigned long long foo( unsigned k )
{
    // a 取值 [1,9]
    // b 取值 [0,19],再大的话,超过64bits就溢出了
    unsigned long long pow_10_b = 1;
    for( unsigned i=1; i<20*9; ++i )
    {
        unsigned a = i%9 + 1;
        unsigned b = i/9;
       

        if( a*(pow_10_b-k) % (10*k-1) == 0 )
        {
            unsigned long long c = a*(pow_10_b-k) / (10*k-1);
            return a*pow_10_b+c;
        }

        if( a == 9 )
            pow_10_b *= 10;
    }
    return 0;
}

int main()
{
    printf( "%u\n", foo(4) );
    printf( "%u\n", foo(10) );
    printf( "%u\n", foo(11) );
    printf( "%u\n", foo(99) );
    printf( "%u\n", foo(999) );
    printf( "%u\n", foo(9999) );
   

    return 0;
}

2012-12-14 13:08
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
有解,是取值范围不对,不能用这些整型
2012-12-14 13:13
快速回复:大大们。我又来了。。又是程序超时这让小白头疼的事
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.034545 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved