[九度OJ]题目1087:约数的个数 解题报告 标签(空格分隔): 九度OJ 原题地址:http://ac.jobdu.com/problem.php?pid=1087 题目描述: 输入n个整数,依次输出每个数的约数的个数. 输入: 输入的第一行为N,即数组的个数(N<=1000) 接下来的1行包括N个整数,其中每个数的范围为(1<=Num<=1000000000) 当N=0时输入结束. 输出: 可能有多组输入数据,对于每组输入数据, 输出N行,其中每一行对应上面的一个数的约数的个数.

题目链接: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)个

怎么判断一个数是否为素数? 笨蛋的作法: bool IsPrime(unsigned n){    if (n<2)    { //小于2的数即不是合数也不是素数    throw 0;    }    for (unsigned i=2;i<n;++i)    { //和比它小的所有的数相除,如果都除不尽,证明素数        if (n%i==0)        {//除尽了,则是合数            return false;        }    }    return tr

题目: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 "今有物不知其数,三三数之有二,五五数之有三,七七数之有

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

一,问题描述 给定100万个区间对,假设这些区间对是互不重叠的,如何判断某个数属于哪个区间? 首先需要对区间的特性进行分析:区间是不是有序的?有序是指:后一个区间的起始位置要大于前一个区间的终点位置.如:[0,10],[15,30],[47,89],[90,100]…..就是有序的区间[15,30],[0,10],[90,100],[47,89]……就是无序的区间 其次,区间是不是连续的?连续是指:后一个区间的起始位置 比 前一个区间的终点位置大1,连续的区间一定是有序的.如:[0,10],[1

这类题目,首先需要确定可用内存的大小,然后确定数据的大小,由这两个参数就可以确定hash函数应该怎么设置才能保证每个文件的大小都不超过内存的大小,从而可以保证每个小的文件都能被一次性加载到内存中. 1. 如何从大量的url中找到相同的url? 题目描述:给定a.b两个文件,各存放50亿个url,每个url各占64B,内存限制是4GB,请找出a.b两个文件共同的url. 分析:50亿个url,50亿*64 = 5GB*64=320GB,内存大小4GB,因此不可能一次性把所有的url都加载到内存中处

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

一个数是不是质数,就是判断一个数除了1和它本身还有没有其他的约数,如果有则是合数,否则是质数.其实本质都是求公约数. 求公约数是什么思路呢,就是找比它小的数不断尝试,能被整除则是其约数,否则继续尝试,直到确定所有数都找遍.本着这个思路,求公约数的算法如下: public static List<long> GetGYS(long num) { ) }; ,num}; ,end=num/temp; while(temp<end){ ) list.Add(temp); temp++; end

慢慢化柿子吧 要求的是这个 \[\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

1.约定 x%y为x取模y,即x除以y所得的余数,当x<y时,x%y=x,所有取模的运算对象都为整数. x^y表示x的y次方.乘方运算的优先级高于乘除和取模,加减的优先级最低. 见到x^y/z这样,就先算乘方,再算除法. A/B,称为A除以B,也称为B除A. 若A%B=0,即称为A可以被B整除,也称B可以整除A. A*B表示A乘以B或称A乘B,B乘A,B乘以A--都一样. 复习一下小学数学 公因数:两个不同的自然数A和B,若有自然数C可以整除A也可以整除B,那么C就是A和B的公因数. 公倍数:两

求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij)\) 不知道怎么讲..... 首先考虑\(d(ij)\)究竟是什么 首先,很自然地想到,既然是求\(ij\)的约数个数 因此就枚举\(i,j\)的约数 即\(d(ij) =\sum\limits_{x|i}\sum\limits_{y|j}...\) 注意到,我们不能重复地统计 我们从唯一分解得形式来考虑 因为多个质因子个和一个质因子的情况是一致的 因此我们考虑一个质因子 假设\(i = p^a,

[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1053 [题目大意] 于任何正整数x,其约数的个数记作g(x).例如g(1)=1.g(6)=4. 如果某个正整数x满足:g(x)>g(i) 0<i<x,则称x为反质数. 求不超过N的最大的反质数 [题解] 此题需要用到结论: 1.一个数约数个数=所有素因子的次数+1的乘积 2.小素数多一定比大素数多优. 所以预处理出小素数表,利用搜索解决这个问题 [代码] #include &

洛谷P1463:https://www.luogu.org/problemnew/show/P1463 思路 约数个数公式  ai为质因数分解的质数的指数 定理: 设m=2a1*3a2*...*pak(其中p为第k大的质数)是Antiprime数 则必有a1≥a2≥a3≥...≥ak≥0 因此如果有两个值约数个数相同 则要取值比较小的那个 剪枝: 有了这个定理我们就可以搜索质数的指数 由于231已经远远超过数据规模 因此我们只需要搜到31层 质因子的个数最多只有10个(所有质因子相乘得到他们可以

3994: [SDOI2015]约数个数和 Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 898  Solved: 619[Submit][Status][Discuss] Description  设d(x)为x的约数个数,给定N.M,求     Input 输入文件包含多组测试数据. 第一行,一个整数T,表示测试数据的组数. 接下来的T行,每行两个整数N.M.   Output T行,每行一个整数,表示你所求的答案.   Sample Inp

判断一个数是不是2的几次幂,最简单粗暴的做法就是直接迭代除以2,这里有一个更好的方法,那就是采用位运算. 我们观察下面属于2的几次幂的数的变化规律,用2进制表示. 十进制 二进制 0 0 2 10 4 100 8 1000 16 10000 我们会发现凡是2的几次幂0除外,用二进制表示第一位全是1,后面全是0.这个规律好像是这样但是有什么用呢,不要急,你再看一下比他小一个数的规律就懂了. 十进制 二进制 1 01 3 011 7 0111 15 01111 发现比他小一个数全是第一位为0后面全为

下文中所有讨论都在数论函数范围内开展. 数论函数指的是定义域为正整数域, 且值域为复数域的函数. 数论意义下的和式处理技巧 因子 \[ \sum_{d | n} a_d = \sum_{d | n} a_{\frac n d} \] 双重因子 \[ \sum_{k | n} \sum_{j | k} a_{k, j} = \sum_{k | n} \sum_{j | \frac n k} a_{jk, k} \] \[ \sum_{n | k} \sum_{k | j} a_{k, j} = \

点此看题面 大致题意: 设\(d(x)\)为\(x\)的约数个数,求\(\sum_{i=1}^N\sum_{j=1}^Md(i·j)\). 莫比乌斯反演 这是一道莫比乌斯反演题. 一个重要的性质 首先我们要先了解\(d(i·j)\)这个函数的性质: \[d(i,j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\] 证明: 我也不知道,应该就是枚举\(i\)和\(j\)的约数,求出其中不互质的约数对个数,避免重复计算. 一些定义 按照莫比乌斯反演的常见套路,我们可以定义\(

一.判断一个数是否为小数 1.有且仅有一个小数点 2.小数点的左边可能为正数或负数 3.小数点的右边为正数 二.实现代码 def is_float(str): if str.count('.') == 1: #小数有且仅有一个小数点 left = str.split('.')[0] #小数点左边(整数位,可为正或负) right = str.split('.')[1] #小数点右边(小数位,一定为正) lright = '' #取整数位的绝对值(排除掉负号) if str.count('-')

n的约数个数 题目:t次询问,每次给你一个数n,求在[1,n]内约数个数最多的数的约数个数 数据:对于100%的数据,t <= 500 , 1 <= n <= 1000000000000000000 思路:对前20个质数搜索,质数指数依次递减. 代码: #include "bits/stdc++.h" #define ll long long using namespace std; ; ; ]={,,,,,,,,,,,,,,,}; ll ans,n; void df

Mathematicians love all sorts of odd properties of numbers. For instance, they consider to be an interesting number, since it is the first odd number for which the sum of its divisors is larger than the number itself. To help them search for interest