题目链接 ：

1. 洛谷

2.topoi

、

大致题意：输入一个数s，找出所有约数和为s的数

关于一个数的约数和求法：

一个>1的整数可以被分解为多个 质数 的乘方，设数 s = p1k1 * p2k2 * p3k3  *......*pnkn

根据 组合 的思想  s的约数和 = （p10 +p11+p12+......+p1k1）*（p20 +p21+p22+......+p2k2）*........*（pn0 +pn1+pn2+......+pnkn）;

数据很大，有多组测试数据，首先想到预处理

预处理 2 * 10^9内的所有质数？（神仙也没法阻止你TLE）

事实上只要处理√2*10^9内的质数行了。Why？ 注：√2*10^9 ≈ 50000

设输入的数为s，有一个质数 k>√s， 在分解s的过程中，k最多只能取1个

所以在找答案的过程中，只要判断当前分解的数 a = k + 1（k+k0=k+1）就可以加入答案

但在实际搜索的过程中，假设当前在枚举第 x 个质数，分解的数为 a，当a - 1 > t[x] 且 (a - 1)是质数时，就可以加入答案。

因为如果（a-1）是质数，之后枚举的所有质数 p，一定满足 p * p <= a （前面已经提到只枚举 < √a 的质数），所以 p ≠ a-1，不会造成答案重复

预处理质数 ：

范围虽然开了根号，但用普通筛选肯定不行，（估计TOPOI又要炸了）

这里要用到线性筛来预处理

线性筛主体思想：让每一个数只筛选出部分合数，其余的让别的数来筛，时间复杂度 O(n)

实现：

for (register int i = 2; i <= maxn; i++) {

        if (!ok[i])  t[++num] = i;

        for (register int j = 1; j <= num; j++) {

            if (t[j] * i > maxn) break;

            ok[t[j] * i] = 1;

            if (i % t[j] == 0) break;

        }

    }  //线性筛 预处理 maxn 内的质数

　　

处理出质数后，就可以开始暴力枚举

搜索的时候 从n除到1或从1乘到n都可以 （因为运算符不同， 从n除到1貌似更快一些）

这里附上 2 种做法的代码（差不多）

（代码跟 洛谷里的题解 差不多，毕竟我也是看了题解）

细节看一下代码中的注释吧 （代码巨丑）

代码1：

#include <bits/stdc++.h>

using namespace std;

#define maxn 50000

int n, num, ans[maxn * 2], t[maxn + 10], tot;  //ans存答案，t存质数,tot记录答案数

bool ok[maxn + 10];        //ok表示是否是质数

bool check (int x) {

	if (x <= maxn) return !ok[x];   //优化 ：若这个数已经预处理过，就不用重复做了

	for (register int i = 1; t[i] * t[i] <= x; i++) if (x % t[i] == 0) return false;

	//这里判断质数只要用前面 质数 来判断就行了，节省时间

	return true;

}

void dfs (int x, int sum, int now) {

	if (sum == 1) {ans[++tot] = now;  return;}  //当分解到 1 时说明方案成立，加入答案

	if (sum > t[x] + 1  and check (sum - 1)) ans[++tot] = now * (sum - 1);  //特判是否满足上述情况

	for (register int k = x + 1; t[k] * t[k] <= sum; k++)    //外重枚举质数

		for (register int ss = 1 + t[k], sn = t[k]; ss <= sum; sn *= t[k], ss += sn) {//内重枚举个数

			if (sum % ss != 0) continue;   //剪枝 ：如果除不尽就别做了

			dfs (k, sum / ss, now * sn);

		}

}

int main() {

	for (register int i = 2; i <= maxn; i++) {

		if (!ok[i])  t[++num] = i;

		for (register int j = 1; j <= num; j++) {

			if (t[j] * i > maxn) break;

			ok[t[j] * i] = 1;

			if (i % t[j] == 0) break;

		}

	}  //线性筛 预处理 maxn 内的质数

	while (~scanf ("%d", &n)) {   //~scanf实现多组数据读入

		tot = 0;

		dfs (0, n, 1);

		sort (ans + 1, ans + tot + 1);

		printf ("%d\n", tot);

		for (register int i = 1; i <= tot; i++) printf ("%d ", ans[i]);

		if (tot) puts ("");

	}

	return 0;

}

代码2：

#include <bits/stdc++.h>

using namespace std;

#define maxn 50000

int n, num, ans[maxn * 2], t[maxn + 10], tot;  //ans存答案，t存质数,tot记录答案数

bool ok[maxn + 10]; //ok表示是否是质数

bool check (int x) {

	if (x <= maxn) return !ok[x];   //优化 ：若这个数已经预处理过，就不用重复做了

	for (register int i = 1; t[i] * t[i] <= x; i++) if (x % t[i] == 0) return false;

	//这里判断质数只要用前面 质数 来判断就行了，节省时间

	return true;

}

void dfs (int x, int sum, int now) {

	if (sum == n) {ans[++tot] = now;  return;}   //当乘积到 n 时说明方案成立，加入答案

	if (n / sum > t[x] + 1  and check (n / sum - 1)) ans[++tot] = now * (n / sum - 1);  //特判是否满足上述情况

	for (register int k = x + 1; t[k] * t[k] <= n / sum; k++)   //外重枚举质数

		for (register int ss = 1 + t[k], sn = t[k]; ss <= n / sum; sn *= t[k], ss += sn) { //内重枚举个数

			if ((n / sum) % ss != 0) continue; //剪枝 ：如果除不尽就别做了

			dfs (k, sum * ss, now * sn);

		}

}

int main() {

	for (register int i = 2; i <= maxn; i++) {

		if (!ok[i])  t[++num] = i;

		for (register int j = 1; j <= num; j++) {

			if (t[j] * i > maxn) break;

			ok[t[j] * i] = 1;

			if (i % t[j] == 0) break;

		}

	}  //线性筛 预处理 maxn 内的质数

	while (~scanf ("%d", &n)) {   //~scanf实现多组数据读入

		tot = 0;

		dfs (0, 1, 1);

		sort (ans + 1, ans + tot + 1);

		printf ("%d\n", tot);

		for (register int i = 1; i <= tot; i++) printf ("%d ", ans[i]);

		if (tot) puts ("");

	}

	return 0;

}

　　

点一下左边的推荐吧！谢谢~~~

最新文章

  1. JAVA6开发WebService （四）——SAAJ调用WebService
  2. BroadcastReceiver和EventBus区别是什么
  3. Dapper试用
  4. Android系统的常用权限
  5. Wireless Network
  6. BISTU-(1)-4-17-2016
  7. eclipse 中忽略jsp, xml文件中的报错信息
  8. php中应该哪怕被打断腿都要记得的几个函数
  9. 利用cmake来搭建开发环境
  10. [翻译]Webpack解惑
  11. DPDK support for vhost-user
  12. ios开发之xcode环境介绍
  13. Scrapy 1.4 文档 05 命令行工具
  14. 说一说MVC的CSRF(三)
  15. 原生js及H5模拟鼠标点击拖拽
  16. iOS如何在应用中添加图标更换功能
  17. luogu2312 [NOIp2015]解方程 (秦九韶)
  18. Android Studio下添加assets目录
  19. Swift - 添加纯净的Alamofire
  20. 【图文教程】WebStorm下使用Github下载以及上传代码

热门文章

  1. hdu-5652 India and China Origins(二分+bfs判断连通)
  2. 【构建二叉树】01根据前序和中序序列构造二叉树【Construct Binary Tree from Preorder and Inorder Traversal】
  3. [原]NYOJ-房间安排168
  4. pthread_detach()函数
  5. 使用NSURLProtocol和NSURLSession拦截UIWebView的HTTP请求(包括ajax请求)
  6. script加载之defer和async
  7. windows拾遗
  8. office2016_windows永久激活查看方法
  9. POJ1365:质因数分解
  10. 【转】 Pro Android学习笔记（三九）：Fragment（4）：基础小例子-续