首页 > 其他分享 >φ(* ̄0 ̄)3337. poj1845 sumdiv题解

φ(* ̄0 ̄)3337. poj1845 sumdiv题解

时间:2024-04-19 23:24:16浏览次数:25  
标签:a% int 题解 sumdiv return above log2 poj1845 5e7

遇到数论题就要推式子!

提供最美丽的latex

\[a^b=p_1^{a_1*b}*p_2^{a_2*b}*p_3^{a_3*b}......*p_n^{a_n*b} \\ 那么他的因数之和为: \\( {p_1}^0+ {p_1}^1+...+ {p_1}^{a_1*b}) \\*( {p_2}^0+ {p_2}^1+...+ {p_2}^{a_2*b}) \\... \\*( {p_n}^0+ {p_n}^1+...+ {p_n}^{a_n*b}) \\=> 利用等比数列:{p_1^{{a_1*b}+1}-1\above 1pt p_1-1}* {p_2^{{a_2*b}+1}-1\above 1pt p_2-1}... {p_n^{{a_n*b}+1}-1\above 1pt p_n-1} \]

分析时间复杂度

\[\sqrt a:分解 \\log2(a)*log2(b):快速幂 \\log2(a):逆元 \\ \sqrt{5e7}*(log2(5e7)+log2(5e7) \\≈7071*(26+26) \\=特别快 \]

ACcode

#include<bits/stdc++.h>
using namespace std;
int x,y,a,b,cnt,flag,m=9901;
void ojld(int a,int b){
	if(!b){
		x=1;
		y=0;
		return;
	}
	ojld(b,a%b);
	int t=y;
	y=x-a/b*t;
	x=t;
	return;
}
int pw(int a,int b){
	int sum=1;
	while(b){
		if(b&1){
			sum=(sum%m*a%m+m)%m;
		} 
		b>>=1;
		a=(a%m*a%m+m)%m;
	}
	return sum%m;
}
signed main(){
	cin>>a>>b;
	int ans=1;
	for(int i=2;a!=1;i++){
		int zhi=0;
		if(a%i==0){
			while(a%i==0){
				a/=i;
				zhi++;
			}
		}
		else{
			continue;
		}
		int fz,fm;
		fz=(pw(i,zhi*b+1)-1+m)%m;
		int t=i-1;
		ojld(t,m);
		fm=(x%m+m)%m;
		ans=(ans%m*fz%m*fm%m+m)%m;
	}
	cout<<ans%m;
	return 0;
}

标签:a%,int,题解,sumdiv,return,above,log2,poj1845,5e7
From: https://www.cnblogs.com/lewisak/p/18146979

相关文章

  • 「NOIP2012」同余方程 题解!!
    嗨嗨嗨!又是我想写这道题,我们就需要掌握:拓展欧几里得顾名思义,它就是欧几里得算法(人话:辗转相除法)的proMax版本别告诉我你不会辗转相除法拓展欧几里得的作用是求对于方程\[a*x+b*y=gcd(a,b)\]解出x,y的值。让我们一步步分析!贴个辗转相除板子先:voidojld(inta,intb){ i......
  • poj3696 The Luckiest number 题解
    很容易想到,\(n\)个8可以转换为\((10^{n+1}-1)/9*8\)容易你个集贸啊,xzz推10分钟我推了一个上午顺便膜拜xzz然后就是推式子了。。。(悲\[(10^{n+1}-1)/9*8\equiv0\pmodh\\=>{10^{n+1}*8-8\above1pt9}\equiv0\pmodh\\=>10^{n+1}*8-8\equiv0\pmod{9h}\\=>10^{n+1}*8\e......
  • P321. [NOI2002]荒岛野人Savage题解?!!!
    还是我容易(☚xzz说的)想出,x年后i号野人的位置为:\((C_i+P_i*x)\modm\)我们只要让任意方程:\((C_i+P_i*x)\modm=(C_j+P_j*x)\modm\)解小于\(L_i\)或小于\(L_j\)即可推式子!\[(C_i+P_i*x)≡(C_j+P_j*x)\(mod~m)\\⇿x*(P_i-P_j)+y*m=C_j-C_i\]然后就是拓展欧几里得模板了。......
  • 题解:CSP-S2020] 函数调用
    题解:CSP-S2020]函数调用一句话题意:给定一个有初始值的序列,支持如下三种操作:1、单点加2、全局乘3、递归某些操作1、2、3求最终的序列。标签:topsort,动态规划,转化贡献统计(集中贡献),主客翻转关于topsort:部分分里的树结构基本上直接暗示了正解要使用topsort,而且本来函......
  • CF1713F Lost Array 题解
    题目链接点击打开链接题目解法很牛的题!!!先考虑\((0,i)\)对\((j,n)\)的贡献,因为是异或,所以只要考虑奇偶性问题可以抽象成一条路径对应\(a_i\)的贡献,所以是否有\(a_i\)的贡献看\(\binom{n-i+j-1}{j-1}\)的奇偶性根据\(kummer\)定理,这个组合数是奇数当且仅当\(n-i+......
  • [题解][洛谷P1412] 经营与开发
    题目描述给定n,k,c,w,然后输入n组数据,数据分为两种:1ai:可以选择获得aiw的价值,但w会变成w(1-0.01*k)2bi:可以选择损失biw的价值,但w会变成w(1+0.01*c)求可获得的最大价值是多少。题解看到这个题,我的第一思路是求后缀和,然后让新得到的系数乘后缀和判断是否进行操作。但问题在于,对于......
  • 高斯消元学习笔记——P304题解
    如果你觉得这篇太啰嗦问题[SDOI2006]线性方程组题目描述已知\(n\)元线性一次方程组。\[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\\cdots\\a_{n,1}x_1+a_{n,2}x......
  • ABC349F题解
    思想看到LCM想到质因数分解。首先,我们先把\(M\)质因数分解了,根号复杂度刚好1e8级别。然后我们发现一个很显然的性质:如果一个数不是\(M\)的因数那他肯定没用。所以此处我们就把不是因数地踢掉。我们惊奇地发现因为\(M\)的质因数分解最多\(13\)个不同的质数,然后我......
  • 题解 LGP5397【[Ynoi2018] 天降之物】/ 第四分块
    题解P5397【[Ynoi2018]天降之物】/第四分块题目描述一个长为\(n\)的序列\(a\)。你需要实现\(m\)个操作,操作有两种:把序列中所有值为\(x\)的数的值变成\(y\)。找出一个位置\(i\)满足\(a_i=x\),找出一个位置\(j\)满足\(a_j=y\),使得\(|i-j|\)最小,并输出\(|i-......
  • vsCode无法连接服务器问题解决及思考
    背景早上刚打开电脑,准备开始一天的工作。但是发现VSCode无法连接上我的虚拟机了,导致无法工作了,这让我十分头疼。最终花了将近一天的时间将问题解决,但是其中的过程走了不少弯路,浪费了不少时间,也进行了反思。我们作为开发人员,应该要用软件思维去理解这款产品,帮助我们去思考问题。......