POJ 1845 Sumdiv

mac2022-06-30  131

超时超时一定要注意不要超时啊!!

题目大意:

给两个数a,b,求a的b次方的所有约数的和对9901取余的值。

解题思路:

a可以分解成多个素数相乘的的形式,这些素数可能有些相同,所以就成了以下形式:

 a=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)

其中pi为素数,因为有可能相同例如8=2^3,所以写成了pi的ki次方形式。

a的约数之和就是:

(1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1+p3+ p3^3+…+ p3^k3) * .... (1+pn+pn^2+pn^3+...pn^kn)

那么a的b次方的约数之和就是:

 [1+p1+p1^2+...+p1^(k1*b)] * [1+p2+p2^2+...+p2^(k2*b)] *...* [1+pn+pn^2+...+pn^(kn*b)]

只需要快速的实现这一些计算就能过。

需要注意的是:

1、经过测试,后台数据每个文件只有一组数据,也就是说代码中不需要写以文件结尾。但是数据文件有多个,

这也就是说每测试一组数据后台都要重跑一边代码。打素数表来生成素数的解题方式不适用于这样的测试方式

需要用更高效的方法来生成素数。

代码中用的方法:

首先对2进行特殊处理,因为除了2之外的所有偶数都不是素数,

i从3开始循环,每次加2对a取余,判断是否整除。如果能整除,一直除到不能整除。

如果这个数是合数,一定不会整除a,因为如果那样的话,他的质因数就可以整除a,就没除干净,这是不可能的,所以每次操作一定是素数的操作。

2、对于处理pi的ki*b次方不能枚举ki*b次,因为ki*b用可能是一个10的10次方以上的数,那样的话单这一次就超时了。需要用另一种方法,我们来举个例子: 2的4次方可以转化成4的2次方,2的5次方可以转化成4的2次方成2。

具体实现见代码。

3、处理[1+p1+p1^2+...+p1^(k1*b)] 也不能枚举指数,同前面第二条的原因是一样的。我们需要这样解决:

对于n项1+p1+p1^2+...+p1^n来说,

当n是偶数时: (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);对于前面的 (1 + p + p^2 +...+ p^(n/2-1)) 还可以继续递归计算。

当n是奇数时:(1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1));对于前面的 (1 + p + p^2 +...+ p^(n/2)) 还可以继续递归计算。

4、运算过程中用longlong,对a的值为0,1,b的值为1,进行特判减少运算,运算过程中用同余模定理控制运算中变量数值的大小。

下面是代码:

#include <stdio.h> #define N 10000000 int noc=0; struct node { int x,y; } node[10000]; long long power(long long p,long long n) { long long yu=1; while(n) { if(n%2) yu=(yu*p)
转载请注明原文地址: https://mac.8miu.com/read-4215.html
最新回复(0)