$loj530\ [LibreOJ\ \beta\ Round \#5]$ 最小倍数 数论

正解:数论

解题报告:

传送门$QwQ$!

不想做题,来水点儿简单点的$QwQ$.

一个显然的点在于可以直接对不同质因子分别算$n_{min}$最后取$max$.

这个正确性还是蛮显然的?因为只要有$n\geq n_{min}$就一定能整除这个质因子呗$QwQ$.

现在就只要分别求这个$n_{min}$了

考虑二分呗,然后$n!$中$x$的指数之和就是$\sum \frac{n}{x^i}$

$over$

一个优化是从大到小枚举这个$pr$这样二分的次数少些计算就少些,不然会$T$,$QAQ$.

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ll long long
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=1e4;
int pr[N+],pr_cnt;
ll a[N];
bool is_pr[N+];

il ll read()
{
    ll x=;rb y=;rc ch=gc;
    while(ch!='-' && (ch>'' || ch<''))ch=gc;
    if(ch=='-')y=,ch=gc;
    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
    return y?x:-x;
}
il void pre(){rp(i,,N)if(!is_pr[i]){if(pr_cnt<)pr[++pr_cnt]=i;for(ri j=1ll*i*i;j<=N;j+=i)is_pr[j]=;}}

int main()
{
    //freopen("530.in","r",stdin);freopen("530.out","w",stdout);
    pre();ri T=read();
    while(T--)
    {
        ri m=read();ll as=;
        rp(i,,m)a[i]=read();
        my(i,m,)
        {
            ll l=as,r=1ll*a[i]*pr[i];//printf("l=%lld r=%lld %lld*%d\n",l,r,a[i],pr[i]);
            while(l<r)
            {
                ll mid=(l+r)>>,t1=,t2=mid;while(t2 && t1<a[i])t2/=pr[i],t1+=t2;
                if(t1>=a[i])r=mid;else l=mid+;
            }
            as=max(as,l);
        }
        printf("%lld\n",as);
    }
    return ;
}

随机推荐

1. BUAA 623 Chem is Try！

   http://oj55.bianchengla.com/problem/623/ 好久没写过题解了,昨天做了一道挺恶心的题目,贴一下代码上来.看了一下提交状况,好像我的代码挺短的了,至少我找不到比我短 ...

2. oracle函数 trunc(x[,y])

   [功能]返回x按精度y截取后的值 [参数]x,y,数字型表达式,如果y不为整数则截取y整数部分,如果y>0则截取到y位小数,如果y小于0则截取到小数点向左第y位,小数前其它数据用0表示. [返回 ...

3. 怎么清除火狐浏览器的cookie？

   火狐浏览器清除Cookie方法/步骤 1.打开火狐浏览器.并在火狐浏览器工具栏找到并单击“工具”下的“选项”. 2.在打开的“火狐浏览器选项”程序窗口中,找到工具栏中的“隐私”并单击,在隐私选项下找到 ...

4. python selenium 基础框架

   base_page.py # coding=utf-8 import time from selenium.common.exceptions import NoSuchElementExceptio ...

5. LightOJ 1123 Trail Maintenance

   题意:n个城市m天.每一天修一条道路,输出当前天数的最小生成树,但是这里有一个条件,就是说最小生成树必须包括全部n个城市,否则输出-1 思路:边数有6000如果每一天跑一次最小生成树的话就接近O(m^ ...

6. pip 将 某包指定到某目录 安装

   pip 将 某包指定到某目录  安装: pip install --target=d:\somewhere\other\than\the\default package_name

7. artTemplate模版引擎的使用

   artTemplate: template.js 一款 JavaScript 模板引擎,简单,好用.提供一套模板语法,用户可以写一个模板区块,每次根据传入的数据,生成对应数据产生的HTML片段,渲染不 ...

8. 2013-10-7 设置combboxItem高度的方法

   //首先设置一个较大的 ItemHeight 值,比如 20: //然后设置 ComboBox 的 DrawMode 为 OwnerDrawVariable: //再设置DrawItem事件如下 if ...

9. SVN 树冲突解决详解

   https://blog.****.net/xgf415/article/details/75196714 SVN 冲突包括 内容冲突:当两名(或更多)开发人员修改了同一个文件中相邻或相同的行时就会发 ...

10. 获取 Nuget 版本号

    本文告诉大家通过命令行获取 Nuget 的版本号 在 Nuget 中没有 -version 和 -v 和 --version 等写法,只需要直接输入 nuget 在第一行就会显示版本号 nuget N ...