专栏首页饶文津的专栏【HDU5778】abs(数学)

【HDU5778】abs(数学)

题意

题解

因为每个质因子出现两次,所以y一定可以开根号。于是我们枚举sqrt(x)附近的sqrt(y),质因子都只出现一次就是可行的。比赛的时候我是打好质数表,然后枚举质因子。实际上直接枚举还更快。

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
int n;
ll a,ans;
bool ck(ll x){
	if(x<2)return 0;
	for(int i=2;i*i<=x;i++)
		if(x%(i*i)==0)return 0;
	ans=min(ans,abs(x*x-a));
	return 1;
}
int main() {
	scanf("%d",&n);
	while(n--){
		ans=1LL<<60;
		scanf("%lld",&a);
		ll b=sqrt(a),c=b;
		for(b++;ck(b)+ck(c)==0;b++,c--);
		printf("%lld\n",ans);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【USACO 1.4】Combination Lock

    饶文津
  • 【UVA 11401】Triangle Counting

    以i 为最大边,第二边为i-1、i-2、...2 的三角形分别有 i-2个、i-3、... 、1个,总共就有(i-1)*(i-2)/2个。有(i-1)/2条边算...

    饶文津
  • 【HDU - 4344】Mark the Rope(大整数分解)

    饶文津
  • 【蓝桥杯】ADV-204 快速幂

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • CCPC-Wannafly Winter Camp Day2 A. Erase Numbers II

    题目链接:https://www.zhixincode.com/problem/day2-2

    Ch_Zaqdt
  • 【HDU - 4344】Mark the Rope(大整数分解)

    饶文津
  • FFmpeg编解码处理3-视频编码

    编码使用avcodec_send_frame()和avcodec_receive_packet()两个函数。

    用户4940323
  • 【PAT乙级】单身狗

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • javascript正则表达式入门先了解这些

      当执行写操作后,需要保证从缓存读取到的数据与数据库中持久化的数据是一致的,因此需要对缓存进行更新。

    不会飞的小鸟
  • 12:计算2的N次方

    12:计算2的N次方 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 任意给定一个正整数N(N<=100),计算2的n次方...

    attack

扫码关注云+社区

领取腾讯云代金券