#include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 1000005 bool vis[maxn]; int m,primes[maxn]; void init(){ ;i<maxn;i++){ if(!vis[i]) primes[++m]=i; ;j<=m;j++){ if(primes[j]*i>=maxn)break; vis[primes[j]*i]=; )bre

一个数的正约数个数等于这个数的质因数分解后 每一项幂+1的积 因为每个质因数的幂可以为0, 1, 2--(注意可以为0) 所以就每个质因数配一个幂任意组合就可得一个正因数,根据乘法原理可得正约数个数. 另外质因数分解可以不用素数筛(但可能会稍微慢一点) #include<cstdio> #define REP(i, a, b) for(int i = (a); i < (b); i++) using namespace std; int f(int n) { int ret = 1; f

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4542 小明系列故事--未知剩余系 Time Limit: 500/200 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 889    Accepted Submission(s): 207 Problem Description "今有物不知其数,三三数之有二,五五数之有三,七七数之有

[BZOJ3994]约数个数和(莫比乌斯反演) 题面 求\[\sum_{i=1}^n\sum_{j=1}^md(ij)\] 多组数据\((<=50000组)\) \(n,m<=50000\) 其中\(d(x)\)是\(x\)的约数个数 题解 orz ZSY 巨佬 根据玄学(我也不知道为什么)的公式 \[d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\] 所以,所求等于 \[\sum_{i=1}^n\sum_{j=1}^m\sum_{u|i}\sum_{v|j}[

慢慢化柿子吧 要求的是这个 \[\sum_{i=1}^N\sum_{j=1}^Md(ij)\] 神奇的约数个数函数有一个这样的性质 \[d(ij)=\sum_{x|i}\sum_{y|j}[(x,y)=1]\] 试着从唯一分解定理的角度去理解,将\(i,j\)分别分解质因数 显然\(d(ij)\)应该等于每一个\(p\)在\(i,j\)中分解出来的指数加起来加1再相乘 所以分别枚举所有约数的话,保证这对约数互质就可以求出所有约数了 之后现在的答案变成了 \[\sum_{i=1}^N\sum_{j

题面: 传送门 思路: 首先,我们需要证明一个结论:d(i*j)等于sigma(gcd(x,y)==1),其中x为i的约数,y为j的约数 对于nm的每一个质因子pi分别考虑,设n = pi^ai + n',m = pi^bi + m' 那么显然质因子pi对d(nm)的贡献为(ai+bi+1) 同理,考虑右边的式子,我们发现质数pi对右侧做的贡献仍然是(ai+bi+1),即如下的(x,y) (pi^ai,1) (pi^(ai-1),1) ..... (1,1) .....(1,pi^(bi-1))

Portal Description 共\(T(T\leq5\times10^4)\)组数据.给出\(n,m(n,m\leq5\times10^4)\),求\[\sum_{i=1}^n\sum_{j=1}^m\sigma_0(ij)\] Solution 首先有结论:\(\sigma_0(xy)=\sum_{d_1|x}\sum_{d_2|y}[gcd(d_1,d_2)=1]\).下面先证明一下这个结论. 将\(x,y\)分解质因数,得到\(x=\prod_{i=1}^kp_i^{a_i}\),

题意: \(T(1 \le T \le 50000)\)次询问,每次给出\(n, m(1 \le n, m \le 50000)\),求\(\sum_{i=1}^{n} \sum_{j=1}^{m} d(ij)\),其中\(d(n)\)表示\(n\)的约数个数 分析 有个结论: $$\sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = \sum_{x_1}^{y_1} \sum_{x_2

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1492 这里先讲一下约数个数定理: 对于正整数x,将其质因分解为 x = pow(p1, a) * pow*(p2, b) * pow(p3, c) * ... 则其约数个数为:num(x) = (a+1) * (b+1) * (c+1) *... 推导: 由约数定义可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1 ,共(a1+1)个;同理p2^a2的约数有(a2+1)个

题目链接 题意:输入两个整数L,U(L <= U <= 1000000000, u - l <= 10000),统计区间[L,U]的整数中哪一个的正约数最多,多个输出最小的那个 本来想着用欧拉函数,打个表求所有的约数个数,但是u太大,直接暴力求解 利用唯一分解定理,刷选出根号1000000000的素数,对l,u区间的每一个数进行分解 #include <iostream> #include <cstdio> #include <algorithm> #

Description  设d(x)为x的约数个数,给定N.M,求     Input 输入文件包含多组测试数据. 第一行,一个整数T,表示测试数据的组数. 接下来的T行,每行两个整数N.M.   Output T行,每行一个整数,表示你所求的答案.   Sample Input 2 7 4 5 6 Sample Output 110 121 HINT 1<=N, M<=50000 1<=T<=50000   这篇blog讲得很不错http://blog.codebursts.co

Description 设\(d(x)\)为\(x\)的约数个数,给定\(N,M\),求\[\sum_{i=1}^{N}\sum_{j=1}^{M}d(ij)\]. Input 输入文件包含多组测试数据. 第一行,一个整数\(T\),表示测试数据的组数. 接下来的\(T\)行,每行两个整数\(N,M\). Output \(T\)行,每行一个整数,表示你所求的答案. Sample Input 2 7 4 5 6 Sample Output 110 121 HINT \(1 \le N, M \l

Description  设d(x)为x的约数个数,给定N.M,求     Input 输入文件包含多组测试数据. 第一行,一个整数T,表示测试数据的组数. 接下来的T行,每行两个整数N.M.   Output T行,每行一个整数,表示你所求的答案.   Sample Input 2 7 4 5 6 Sample Output 110 121 HINT 1<=N, M<=50000 1<=T<=50000     数论……终于还是的在神犇博客的帮助下才写得出……T_T…… 最后推出

2015 题意:\(d(i)\)为i的约数个数,求\(\sum\limits_{i=1}^n \sum\limits_{j=1}^m d(ij)\) \(ij\)都爆int了.... 一开始想容斥一下用\(d(i)\)和\(d(j)\)算\(d(ij)\),发现不行... 然后翻题解看到了一步好神的转化: \[ d(nm) = \sum_{i\mid n} \sum_{j\mid m} [gcd(i,j)=1] \] 晚上再补吧还是没拿草稿纸... 补: \(Proof.\) 首先注意约数个数

Sol 首先有个结论 \(\sum_{i=1}^{m}\sum_{j=1}^{n}d(i*j)=\sum_{i=1}^{m}\sum_{j=1}^{n}\sum_{x|i}\sum_{y|i}[gcd(x,y)==1]\) 证明:可以看po姐的博客 接着这个式子推 \[ 原式=\sum_{x=1}^{n}\sum_{y=1}^{m}([gcd(x, y)==1] * \sum_{x|i}\sum_{y|i} 1)\\ =\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x, y)

Description  设d(x)为x的约数个数,给定N.M,求 $\sum^N_{i=1}\sum^M_{j=1}d(ij)$ Input 输入文件包含多组测试数据. 第一行,一个整数T,表示测试数据的组数. 接下来的T行,每行两个整数N.M. Output T行,每行一个整数,表示你所求的答案. Sample Input 2 7 4 5 6 Sample Output 110 121 HINT 1<=N, M<=50000 1<=T<=50000 题解 先给出一个结论: $$

BZOJ_3994_[SDOI2015]约数个数和_莫比乌斯反演 Description  设d(x)为x的约数个数,给定N.M,求   Input 输入文件包含多组测试数据. 第一行,一个整数T,表示测试数据的组数. 接下来的T行,每行两个整数N.M. Output T行,每行一个整数,表示你所求的答案. Sample Input 2 7 4 5 6 Sample Output 110 121 HINT 1<=N, M<=50000 1<=T<=50000 基本同BZOJ4176

P4714 「数学」约数个数和 题意(假):每个数向自己的约数连边,给出\(n,k(\le 10^{18})\),询问\(n\)的约数形成的图中以\(n\)为起点长为\(k\)的链有多少条(注意每个点都有自环) 这样想是做不出来题的. 正常的题意是:询问\(n\)的约数的约数的....(共\(k\)次复读后)约数个数和. 考虑\(f_k(n)\)表示答案. 显然有\(f_{k}(n)=\sum_{d|n}f_{k-1}(d)\) 注意到用数论卷积的形式可以表示为 \[ \mathtt f_k=\

Problem bzoj3994 洛谷3327 题意:设 \(d(x)\) 为 \(x\) 的约数个数,给定 \(N,M\),求\(\sum_{i=1}^N\sum_{j=1}^Md(ij)\) \(1\leq N,M,T\leq 5\times 10^4\) Solution 第一次推出莫反式 ♪(^∇^*) 以下部分中小括号代表\(\gcd\),中括号代表取布尔值 一开始想枚举约数然后看有多少倍数出现过的,发现不好弄,转而想到 \(xy\) 的因数一定是 \(x\) 的因数和 \(y\) 的

又是恶心的莫比乌斯反演,蒟蒻我又是一脸懵逼的被CXR dalao狂虐. 题目要求\(ans=\sum_{i=1}^n \sum_{j=1}^m d(ij)\),其中\(d(ij)\)表示数\(x\)的约数个数 这道题的一大难点就在于\(d(ij)\)这个函数,它有一个重要的性质: \[d(ij)=\sum_{x|i}\sum_{y|i}[\gcd(i,j)=1]\] 大致的证明思路就是对于\(i,j\)的所有约数,为了避免重复计算,我们只取互质的一对. 知道了这个就是反演的套路了(如果不知道为什

http://www.lydsy.com/JudgeOnline/problem.php?id=3994 (题目链接) 题意 多组询问,给出${n,m}$,求${\sum_{i=1}^n\sum_{j=1}^m d(i×j)}$,${d(i×j)}$为${ij}$的约数个数. Solution 看到这个式子感觉无从下手,这个${d(ij)}$比较丑,有一个比较经典的公式:$${d(nm)=\sum_{i|n}\sum_{j|m} [gcd(i,j)=1]}$$ 这个是怎么得来的呢.每一个${nm