首页 > 其他分享 >B3716 分解质因子 3

B3716 分解质因子 3

时间:2024-05-07 14:35:38浏览次数:27  
标签:int cout B3716 ll vis 因子 分解 ans

原题链接

题解

1.数组最大能开到1e8
2.vector比数组容易mle
3.筛素数的时间复杂度是O(n)
4.由于一个数最多有 \(log_2(n)\) 个因子,我们标记每一个合数的最小质因子,然后直接除就行(递归思想?)

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> prime;
int vis[100000005]={0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    for(ll k=2;k<=1e8+4;k++)
    {
        if(!vis[k]) prime.push_back(k);
        for(ll i=0;i<prime.size()&&prime[i]*k<=1e8+2;i++)
        {
            vis[k*prime[i]]=prime[i];
            if(k%prime[i]==0) break;
        }
    }


    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll ans=0;
        while(vis[n])
        {
            ans^=vis[n];
            n/=vis[n];
        }
        ans^=n;
        cout<<ans<<"\n";
    }
    return 0;
}

标签:int,cout,B3716,ll,vis,因子,分解,ans
From: https://www.cnblogs.com/pure4knowledge/p/18177147

相关文章

  • SVD奇异值分解
    利用矩阵SVD分解,拟合直线与平面SVD分解奇异值分解(SingularValueDecomposition,以下简称SVD)就是解决最小二乘法的利器,它不仅可以拟合直线、平面,还可以得到点云的最小包围盒。关于SVD与最小二乘的数学原理和关联,可以直接网上搜索查找,资料大把。本文主要讲解其几何意义和代......
  • [学习笔记] 质数与唯一分解定理 - 数论
    素性测试素性测试就是判断某个数是否为质数。费马小定理内容:若\(p\)为质数,\(a\)为任意整数,有\(a^{p-1}\equiv1(mod\p)\)那么可以多次随机取一个基数\(a\in(1,p)\)若\(p\)满足上式,那么它为质数的可能性就越大。MillarRabin素性测试inlinellqpow(lla,lln,ll......
  • 【模板】分解质因数 Pollard-Rho
    参见洛谷模板题题解,这里只有代码实现。一些强数据参考(输出了最大质因子)79223372036854775783Prime9223371994482243049303700049392232532901085832072097143214748364822147483647Prime21471175694633721417005691289#include<bits/stdc++.h>usingnamespace......
  • 下列不属于分解测试点时的关注点的是( )
    选项:A、性能B、⽆充分理由的揣测C、偶然的设计失误D、可测性答案:BC解析:验证空间是⼀个⽆限集合,我们不可能细化到所有的元素,这就需要我们在分解时重视⼀些主要的关注点,同时忽略掉⼀些不必要的⾮关注点,1、测试点主要关注:a)功能的正确;b)功能、性能点的覆盖;c)发现设计错......
  • AI agent智能体任务分解和调度的几篇经典文章
     ReAct论文解读:LLMReAct范式,在大语言模型中结合推理和动作最近在研究如何让GPT正确做动作,比如搜索内容,发现了《SYNERGIZINGREASONINGANDACTINGINLANGUAGEMODELS》这篇论文。作者提出了ReAct范式,通过将推理和动作相结合来克服LLM胡言乱语的问题,同时提高了结果的可解释性......
  • AI agent中的任务分解和调度-学术界文章汇总
    Reflexion:LanguageAgentswithVerbalReinforcementLearning该文章的要点和关键技术,算法流程该文章提出了一种名为"Reflexion"的新型框架,用于通过语言反馈来强化语言智能体的学习。主要包含以下几个关键点:框架组成:Actor模型:基于大语言模型生成文本和动作E......
  • Lyndon 分解
    作用把一个大字符串分成好多个小字符串这些小字符串的最小后缀,就是其本身求出这些小字符串的右端点下标#include<bits/stdc++.h>usingnamespacestd;chars[5000005];intn,ans;vector<int>a;intmain(){ scanf("%s",s+1); n=(int)strlen(s+1); intx; for(inti=......
  • PiSSA :将模型原始权重进行奇异值分解的一种新的微调方法
    我们开始看4月的新论文了,这是来自北京大学人工智能研究所、北京大学智能科学与技术学院的研究人员发布的PrincipalSingularValuesandSingularVectorsAdaptation(PiSSA)方法。PiSSA和LoRA一样,都是基于这样的前提:对模型参数的改变会形成一个低秩矩阵。这种方法通过将模型中的......
  • 基于矩阵分解的协同过滤算法
    引言随着互联网、大数据等新技术的迅速发展,人们的生活变得更加便捷,但同时也导致网络数据爆炸式增长。为了快速帮助用户找到感兴趣的内容,越来越多的研究者致力于推荐算法的研究,以提高推荐质量,向用户推荐更符合其喜好的内容。然而,目前的推荐算法仍存在数据稀疏性、隐私保护和冷启动......
  • 时序数据分解
    时序数据  时序数据作为与时间强相关数据,有着独特的特点,但是也有很多通用的数据的性质。1.通过数学期望与协方差进行特征相关性的计算;2.平稳性检验  定义上的平稳性指的是固定时间和位置的概率分布与所有时间和位置的概率分布相同的随机过程。其数学期望和方差这......