E 序列求和

本题总分：15 分

---

问题描述

学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并把它定义为 St 。
例如 S1 = 1, S2 = 2, S3 = 4, S4 = 6，· · · 。
现在小明想知道，前 60 个 Si 的和是多少？即 S1 + S2 + · · · + S60 是多少？

---

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

---

先说一下正确答案吧：292809912969717649（此答案到蓝桥杯官网练习系统提交Accept）

说点什么

网上有看到别人说有两种答案，其实说两种答案的都是错的，客观题只有一个答案，他们会说两种答案是因为他们没有理解好题意，题目说的是“总是可以找到含有 t 个约数的整数”，注意理解“t个”的意思，t个即刚好只能是t个，不能多，不能少。
下面说思路
思路有两种，一种是无脑暴搜，另一种则是用数学公式暴搜

---

无脑暴搜

先说一下无脑暴搜，这种思路都是很多人最先想到的，我也是。
但是最后发现很难行得通，懒得看这种行不通的思路的请跳到下面第二种思路的讲解

思路：遍历从1到某个很大的数n，在外层循环遍历到n时判断n有多少个因子t，
	即在内层循环里遍历1到根号n（本来应该再次遍历到n，优化一下，把范围缩小根号n
	（跟判断某个数是不是质数一个道理，这里不再赘述，不懂的百度）），
	内层循环遍历完后再更新用来记录答案的数组result[t]

下面代码
#include<stdio.h>
#include<iostream>
#pragma warning(disable:4996)
using namespace std;

bool vis[1000];
long result[1000];
int main(){
    
		int count = 1;
		for (long i = 1; i < 1000000; i++) {
    
			int temp = 0;
			for (int j = 1; j * j <= i; j++) {
    
				if (i % j == 0) {
    
					if (j * j == i) {
    
						temp++;
					} else {
    
						temp += 2;
					}
				}
			}
			if (vis[temp] == false) {
    
				vis[temp] = true;
				result[temp] = i;
				count++;
			}
		}
		for (int i = 1; i < 60; i++) {
    
			printf("%d ", result[i]);
			if (i % 10 == 0) {
    
				printf("\n");
			}
		}

		bool flag = false;
		printf("\n");
		for (int i = 1; i <= 60; i++) {
    
			if (vis[i] == false) {
    
				printf("%d ", i);
				flag = true;
			}
		}
		printf("\n%d", flag);
}

//1 2 4 6 16 12 64 24 36 48
//1024 60 4096 192 144 120 65536 180 262144 240
//576 3072 4194304 360 1296 12288 900 960 0 720
//0 840 9216 196608 5184 1260 0 786432 36864 1680
//0 2880 0 15360 3600 0 0 2520 46656 6480
//589824 61440 0 6300 82944 6720 2359296 0 0
//发现这几个位置的数一直找不到，即使第一个for循环的i已经达到int无法存储的地步：29 31 37 41 43 46 47 53 58 59
//而且随着i的量级的增加，计算耗时已经达到需要估计十几分钟的地步了，这种暴搜也没什么好优化的，只是小小优化，但耗时还是很长

---

数学公式暴搜

在讲这种思路前需要先跟大家讲一下这个数学公式：

唯一分解定理/算术基本定理
唯一分解定理又称为算数基本定理，基本内容是：

每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

用另一种方法表示就是：

对于任何一个大于1的正整数,都存在一个标准的分解式: N=p1^a1 * p2^a2*···*pnan;（其中一系列an为指数，pn为质数）

此定理表明：任何一个大于 1 的正整数都可以表示为素数的积。

有这样几个式子：

设F(n)代表任意的正整数n的正因子的数量，则F(n)=(a1+1)(a2+1)(a3+1)······(an+1)；

设G(n)代表n的正因子的和，则G(n)=(1+p1^2+p13+…+p1^a1)*(1+p22+p2^3+…p2a2)…(1+pn^1+pn2+…+pn^an)=；

详细的这里不说太多，这里只要需要知道：
1.对于任何一个大于1的正整数都可以分解成若干个质数的积。
2.任意的正整数n的正因子数量t是有公式可求的

思路：
1.首先我们得知道我们需要求的是什么：含有 t 个约数的整数n，因题目需要总和最小，
所以这个n需要在所有含有t个约数的数中最小
2.而根据数学公式我们知道任意的正整数n的正因子的数量t=(a1+1)*(a2+1)*(a3+1)*······*(an+1)；
3.由于n=p1^a1 * p2^a2*···*pn^an;（其中一系列an为指数，pn为质数）,为了是n最小，所以应该使指数a1，a2,a3,...,an从最小的开始遍历
4.遍历时利用公式t=(a1+1)*(a2+1)*(a3+1)*······*(an+1)计算每一种a1,a2,a3,..an的组合情况对应的t为多少，此种情况下n（下面代码中的single变量）为多少，是不是应该更新答案
5.遍历完成后即为答案
（补充:理论上是需要遍历a1,a2,a3,a4,a5,a6,a7...an的所有组合情况的，但是题目只要求取前面60个就行，所以遍历a1,a2,a3,a4就够了，且把每一个指数遍历到100（下面代码中的ii变量）也够了）

package 蓝桥杯真题.第十一届.国赛._5_序列求和;

public class Main {
    

	static int testCount=60;//题目要求计算前60个
	static int ii=100;//每个指数遍历的上限
	static long result[]=new long[61];//用了存放前60个的答案
	public static void main(String[] args) {
    

		for (int a4 = 0; a4 <= ii; a4++) {
    
			for (int a3 = 0; a3 <= ii; a3++) {
    
				for (int a2 = 0; a2 <= ii; a2++) {
    
					for (int a1 = 0; a1 <= ii; a1++) {
    
						
						int t=(a1+1)*(a2+1)*(a3+1)*(a4+1);//计算此种指数组合下的t为多少
						if(t<=60) {
    //稍稍优化一下，大于60的题目不要求计算，优化掉
							long single=(long) (Math.pow(2, a1)*Math.pow(3, a2)*Math.pow(5, a3)*Math.pow(7, a4));//计算此种指数组合下的n为多少
//							System.out.println(a1+" "+a2+" "+a3+" "+a4+"     "+t+" "+single);
							if(single<result[t] || result[t]==0) {
    //n需要在所有含有t个约数的数中最小，所有计算结果比之前小才更新答案
								result[t]=single;
							}
						}
					}
				}
			}
		}
		
		long sum=0;
		for (int i = 1; i <= testCount; i++) {
    
			sum+=result[i];
			System.out.print(result[i]+" ");
			if(i%10==0) {
    
				System.out.println();
			}
		}
		System.out.println("\n"+sum);//最终答案，码字不易，觉得有收获记得点赞评论支持一下
	}
}

//1 2 4 6 16 12 64 24 36 48 
//1024 60 4096 192 144 120 65536 180 262144 240 
//576 3072 4194304 360 1296 12288 900 960 268435456 720 
//1073741824 840 9216 196608 5184 1260 68719476736 786432 36864 1680 
//1099511627776 2880 4398046511104 15360 3600 12582912 70368744177664 2520 46656 6480 
//589824 61440 4503599627370496 6300 82944 6720 2359296 805306368 288230376151711744 5040 
//
//292809912969717649