首页 > 其他分享 >F. Vasilije Loves Number Theory

F. Vasilije Loves Number Theory

时间:2024-07-10 17:20:25浏览次数:14  
标签:prime int Vasilije Number cin while yz Loves ans

原题链接

题解

\(a,n\) 互质,所以 \(d(n·a)=d(a)d(n)\) ,即 \(n\ mod\ d(n)==0\) 是否成立。(总是能构造出一与 \(n\) 互质,且 \(d(a)\) 任意的 \(a\) )
由于 \(n\) 会很大,所以我们将 \(n\) 质因子分解,\(n=p_1^{m_1}p_2^{m_2}...p_k^{m_k}\)
这样一来 \(d(n)=(m_1+1)(m_2+1)...(m_k+1)\)
乘 \(x\) 的时候,将 \(x\) 也进行质因子分解
最后在判断 \(d(n)\) 进行质因子分解,然后判断因子是否足够

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool mark[1000006]={0};
int prime[1000006];


void solve()
{
    int n,q;
    cin>>n>>q;
    int tem=n;
    map<int,int> yz;

    while(n!=1)
    {
        yz[prime[n]]++;
        n/=prime[n];
    }

    while(q--)
    {
        int op;
        cin>>op;
        if(op==2)
        {
            yz.clear();
            n=tem;
            while(n!=1)
            {
                yz[prime[n]]++;
                n/=prime[n];
            }
        }
        else
        {
            int x;
            cin>>x;
            while(x!=1)
            {
                yz[prime[x]]++;
                x/=prime[x];
            }

            ll ans=1;
            for(auto it:yz)
            {
                ans*=(it.second+1);
            }

            bool flag=1;
            for(ll i=2;i*i<=ans;i++)
            {
                if(ans%i==0)
                {
                    int cnt=0;
                    while(ans%i==0)
                    {
                        ans/=i;
                        cnt++;
                    }
                    if(yz[i]<cnt)
                    {
                        flag=0;
                        break;
                    }
                }
            }
            if(ans>1)
            {
                if(yz[ans]<1) flag=0;
            }
            if(flag) cout<<"yes\n";
            else cout<<"no\n";
        }
    }
    cout<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    for(ll i=2;i<=1e6;i++)
    {
        if(!mark[i])
        {
            prime[i]=i;
            for(ll j=i*i;j<=1e6;j+=i)
            {
                if(!mark[i])
                {
                    prime[j]=i;
                    mark[j]=1;
                }
            }
        }
    }
    int t;
    cin>>t;

    while(t--) solve();
    return 0;
}

标签:prime,int,Vasilije,Number,cin,while,yz,Loves,ans
From: https://www.cnblogs.com/pure4knowledge/p/18294600

相关文章

  • Qt:10.显示类控件(QLabel-显示文本或图像的控件、QLCDNumber -显示数字的特殊控件、QPr
    目录一、QLabel-显示文本或图像的控件:1.1QLabel介绍:1.2设置文本格式——textFormat属性:1.3设置图片——pixmap属性:1.4自动缩放——scaledContents属性:拓展:resizeEvent方法:1.5内容对齐方式——alignment属性:1.6自动换行——wordWrap属性:1.7 文本缩进——indent属性......
  • 【Azure App Service】访问App Service应用报错 SSL: WRONG_VERSION_NUMBER
    问题描述应用部署在AzureAppService中,访问DefaultURL,遇见SSL:WRONG_VERSION_NUMBER错误。RESTAPI工具调用时错误信息:writeEPROTO8936192:error:100000f7:SSLroutines:OPENSSL_internal:WRONG_VERSION_NUMBER:..\..\third_party\boringssl\src\ssl\tls_record.cc:231:......
  • 好用的IdCardNumberMethod工具类(直接复制使用)
    packagecom.examine.ythgk.util;importcom.examine.common.core.utils.StringUtils;importjava.text.ParseException;importjava.text.SimpleDateFormat;importjava.util.Calendar;importjava.util.Date;importjava.util.HashMap;importjava.util.Map;impor......
  • JavaScript介绍、初识(注释语法、书写位置、书写规范)、常量和变量、数据类型Number、
    【一】JavaScript介绍【1】什么是jsjs也是一门编程语言,他可以写后端代码【2】什么是node.js前端由于非常受制于后端,所以有一些人异想天开想要通过js来编写后端代码一统江湖由此开发了一个叫nodejs的工具(支持js跑在后端服务器上)但是并不能完美的实现【3】JavaScript......
  • C. Qingshan Loves Strings 2
    原题链接题解1.当10个数不一致时,无论怎样都不成立2.当01个数一致时,是否一定存在某种方法使得成立呢?3.对于长度为\(k\)的字符串\(s\),若不合法,那我在旁边添加一个01,则我们可以连续删除两边的配对数字,且至少能删除一对,且经过若干轮的删除一定能使字符串长度减小总的来说,我们......
  • Atcoder ARC090F Number of Digits
    记\(n\)为题面的\(S\)。能发现对于\(f(l)=8\),共有\(9\times10^7\)个数。此时就已经有\(8\times9\times10^7>10^8=n_{\max}\)了,就说明不存在\(f\ge8\)的情况,还满足这部分对应的数能全被选满。所以可以知道对于\(f(l)\ge8\)的情况,只存在\(f(r)-f(l)=......
  • 0137_Single-Number-II【M】
    JY:找出列表中只出现1次的数值(其它数值均出现3次)参考:https://www.yuque.com/it-coach/leetcode/xkogct1、利用数值二进制位的特性(执行效率并不高)题目中明确了数字的范围是32位整型(-2^31<=nums[i]<=2^31-1),所以从低位遍历到高位,将所有数字的二进制对应位相加,由......
  • C#面:现有一个整数number,请写一个方法判断这个整数是否是2的N次方
    要判断一个整数是否是2的N次方,可以使用位运算来实现。一个整数如果是2的N次方,那么它的二进制表示中只有一位是1,其余位都是0。可以通过将这个整数与它减去1的结果进行按位与运算,如果结果为0,则说明这个整数是2的N次方。以下是一个示例代码:publicboolIsPowerOfTwo(intnumber)......
  • AT_tdpc_number 数 题解
    题目传送门前置知识数位DP|记忆化搜索解法本题的提交在luogu上挂了,建议去原站或Vjudge上提交。基础数位DP,记录当前位置、已填的数码之和,接着记忆化搜索即可。需要注意的是\(0\bmodd=0\),如果写得不太好看(未处理前导零)的话需要减去其贡献。代码#include<bits/......
  • SP8177 JZPEXT - Beautiful numbers EXTREME 题解
    题目传送门前置知识数位DP|同余解法同余的传递性:若\(\begin{cases}a,b\in\mathbf{Z}\\p,q\in\mathbb{N}^{*}\\q|p\end{cases}\),则当\(a\equivb\pmod{p}\)时有\(a\equivb\pmod{q}\)。故在本题中\(\bmod\)各非零数码均等于\(0\)等价于\(\bmod\)各......