| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3229 人关注过本帖
标题:一道时间超限的题,求帮忙优化
取消只看楼主 加入收藏
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
结帖率:92%
收藏
已结贴  问题点数:20 回复次数:4 
一道时间超限的题,求帮忙优化
问题描述
给定一个数x,求正整数y≥2,使得满足以下条件:
1.y-x的绝对值最小
2.y的质因数分解式中每个质因数均恰好出现2次。
输入描述
第一行输入一个整数T(1≤T≤50)
每组数据有一行,一个整数x(1≤x≤10^18)
输出描述
对于每组数据,输出一行y-x的最小绝对值
输入样例
5
1112
4290
8716
9957
9095
输出样例
23
65
67
244
70

代码:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int f(int n){
    int i,k;
    if(n==1) return 1;
    for(i=2;i<=n;i++){
        k=0;
        while(n!=i){
            if(n%i==0){
                n=n/i;
                k++;
                if(k>1) return 0;
            }
            else break;
        }
    }
    return 1;
}
int main(void){
    int T,n,n1,n2;
    long long int x,y1,y2;
    scanf("%d",&T);
    while(T--){
        scanf("%lld",&x);
        n1=sqrt(x);
        n2=n1+1;
        while(!f(n1)) n1--;
        while(!f(n2)) n2++;
        y1=n1*n1;
        y2=n2*n2;
        if(n1!=1)
            printf("%lld\n",((x-y1)>(y2-x))?(y2-x):(x-y1));
        else printf("%lld\n",y2-x);
    }
}

我的思路是先把x开根号,左边整数为y1,右边为y2,判断y1,y2是不是可以分解成每个质因数只出现一次的数,不是的话分别向左右扩散,直到找到。
这个方法显示时间超限了,想问问各位大佬有没有优化的方法?

[此贴子已经被作者于2018-5-18 15:18编辑过]

搜索更多相关主题的帖子: 时间 优化 include int while 
2018-05-18 15:16
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 2楼 九转星河
为什么是完全平方数?
y1,y2必须是能分解成每个质因数只出现一次的数。
比如8,它不是完全平方数,但不符合条件,因为它的质因数是2,2,2,2出现了三次。
2018-05-18 17:41
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 4楼 九转星河
我想的是开根号再比较更好,没想到还是时间超限了
2018-05-18 18:50
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 4楼 九转星河
但是完全平方数也不一定满足条件,比如16是完全平方数,分解质因数后是2,2,2,2,2出现了4次,也不行。每个质因数要么不出现,要么出现两次才行。
2018-05-18 19:02
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 7楼 九转星河
12不是完全平方数,但是144不行,144分解质因数后是2,2,2,2,3,3,2出现了4次
2018-05-18 21:18
快速回复:一道时间超限的题,求帮忙优化
数据加载中...
 
   



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

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