【UOJ#48】【UR #3】核聚变反应强度（质因数分解）

谁践踏了优雅 2021-11-16 09:32 340阅读 0赞

# 【UOJ\#48】【UR \#3】核聚变反应强度（质因数分解） #

## 题面 ##

[UOJ][]

## 题解 ##

答案一定是\\(gcd\\)除掉\\(gcd\\)的最小质因子。  
而\\(gcd\\)的最小值因子一定是\\(a\_1\\)的质因子。  
所以预处理出\\(a\_1\\)的质因子，个数不会超过\\(\\log(a)\\)个，然后就可以直接暴力了。  
时间复杂度\\(O(n\\log(a)+\\sqrt a)\\)

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define ll long long inline ll read() { ll x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x; } int n,tot; ll fac[100000],a[1000100]; ll Calc(ll n) { if(n==1)return -1; for(int i=1;i<=tot;++i) if(n%fac[i]==0)return n/fac[i]; return 1; } int main() { n=read(); for(int i=1;i<=n;++i)a[i]=read(); ll x=a[1]; for(int i=2;1ll*i*i<=x;++i) if(x%i==0) { fac[++tot]=i; while(x%i==0)x/=i; } if(x>1)fac[++tot]=x; for(int i=1;i<=n;++i)printf("%lld ",Calc(__gcd(a[1],a[i]))); puts(""); return 0; }

转载于:https://www.cnblogs.com/cjyyb/p/11051412.html

[UOJ]: http://uoj.ac/problem/48

发表评论取消回复

表情：

评论列表（有 0 条评论，340人围观）

还没有评论，来说两句吧...

相关阅读

相关 uoj22 【UR #1】外星人

[题目][Link 1] 好像虚高胡策搬过这道题设\\(t=\\min a\_i\\)，不难发现我们一旦对\\(t\\)取模之后，就一定小于\\(t\\)，也就是之后再对

冷不防/ 2023年10月11日 05:12/ 0 赞/ 69 阅读

相关质因数分解

一道清华的复试题，我先后看了两份代码，收获匪浅，分别摘自下面两个博客： [https://blog.csdn.net/Little\_Kid\_Kang/article/de

深藏阁楼爱情的钟/ 2023年03月14日 05:54/ 0 赞/ 202 阅读

相关分解质因数

上一篇博客：[质数的筛法][Link 1] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果

Love The Way You Lie/ 2022年10月22日 04:12/ 0 赞/ 284 阅读

相关分解质因数

public class DecomposePrimeFactor \{ public final static int NUM = 154; public static vo

Dear 丶/ 2022年09月30日 06:22/ 0 赞/ 273 阅读

相关分解质因数

问题描述　　求出区间\[a,b\]中所有整数的质因数分解。输入格式　　输入两个整数a，b。输出格式　　每行输出一个数的分解，形如k=a1\a2\a3...(

超、凢脫俗/ 2022年08月05日 02:54/ 0 赞/ 328 阅读

相关分解质因数

题目内容：每个非素数（合数）都可以写成几个素数（也可称为质数）相乘的形式，这几个素数就都叫做这个合数的质因数。比如，6可以被分解为2x3，而24可以被分解为2x2x2x3。

灰太狼/ 2022年07月03日 18:20/ 0 赞/ 320 阅读

相关分解质因数

分解质因数当无法分解是输出“no answer” <table style="font-size:12px; color:rgb(51,51,51); line-heig

淩亂°似流年/ 2022年06月06日 11:42/ 0 赞/ 347 阅读

相关质因数分解

讲一个数分解为几个质数相乘的结果 ![70][] include<cstdio> include<cmath>

末蓝、/ 2022年05月28日 07:58/ 0 赞/ 397 阅读

相关分解质因数

void solution(int num) { int i = 2; while (num != 1) { i

╰半夏微凉°/ 2022年05月09日 01:46/ 0 赞/ 373 阅读

相关【UOJ#48】【UR #3】核聚变反应强度（质因数分解）

【UOJ\48】【UR \3】核聚变反应强度（质因数分解）题面 [UOJ][] 题解答案一定是\\(gcd\\)除掉\\(gcd\\)的最小质因子。

谁践踏了优雅/ 2021年11月16日 09:32/ 0 赞/ 341 阅读