岳阳网站建设哪里有,广州市建设和水务局网站,网站里面送礼物要钱怎么做代码,自己制作简易网页解题思路
80分思路代码 由于题目在数据规模中说明阈值k 1, 因此提取因式时只需要关注次数在二次以上的因式。也就是说#xff0c;我们只需要判断从1到待化简因式的平方根是否是满足题意的因式即可。举个例子#xff0c;假设题目所给因式是10000#xff0c;那么只需要判…解题思路
80分思路代码 由于题目在数据规模中说明阈值k 1, 因此提取因式时只需要关注次数在二次以上的因式。也就是说我们只需要判断从1到待化简因式的平方根是否是满足题意的因式即可。举个例子假设题目所给因式是10000那么只需要判断从1到内是否存在10000的质因式即可因为大于100的质因式一定会被舍去。 再观察数据规模如果输入的因式小于1*10^4那么只需要判断从1到100的质因式即可。小学老师应该要求背过从1到100的质数吧现在就派上用场了。 首先读入查询组数, 定义待处理因式n, 阈值k和输出值output。定义一个质因数数集保存从1到101的27个质因数。定义一个哈希数组保存从1到100质因数的指数并且在每次循环初始化哈希数组。
int q;
cin q;int n, k, output;
int arr[27] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,87,93,97,101};
int temp[102];for(int i 0; i q; i)
{memset(temp, 0, sizeof(int)*102);output 1;cin n k;
... 循环判断从1到101为了保险的27个质因数是否能整除待处理因式n。如果其中一个因数能整除待处理因式那么将该因式从待处理因式分离并在哈希数组中记录该质因数的指数变化。并且继续判断该因数能否被整除直到出现余数。 此时需要看该质因数的指数是否达到阈值。如果达到将相应次数的质因数与输出output相乘。当待处理因式只剩下1的时候退出循环输出output。
for(int j 0; j 27; )
{if(n % (arr[j]) 0){n n / arr[j]; //分离因式temp[arr[j]]; //记录指数continue; //继续看该质因数能否被整除}if(temp[arr[j]] k)output * pow(arr[j], temp[arr[j]]);if(n 1)break;j;
}
cout output endl;
80分完整代码如下其实80分的数据规模达到10^5,理论上以下代码只能保证10^4规模的输出质数只取到101但是官方好像并没有相应的极端数据
#include iostream
#include math.h
#include string.husing namespace std;int main()
{int q, n, k, output;int temp[102];int arr[27] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,87,93,97,101};cin q;for(int i 0; i q; i){output 1;memset(temp, 0, sizeof(int)*102);cin n k;for(int j 0; j 27; ){if(n % (arr[j]) 0){n n / arr[j]; //分离因式temp[arr[j]]; //记录指数continue; //继续看该质因数能否被整除}if(temp[arr[j]] k)output * pow(arr[j], temp[arr[j]]);if(n 1)break;j;}cout output endl;}return 0;
}
100分思路加代码 有了80分的代码做基础其实100分的代码只需要再做一件事把大于1*10^4的数分解为若干个小于1*10^4的数相乘再沿用80分代码分别判断即可。 首先注意数据规模1*10^10的数据需要用长整型long long表示需要把输入输出数据类型都改为long long,并且重新定义一个更长的哈希数组存放指数。
typedef long long LL;
int longtp[10002];
LL n, output; 定义一个返回因数集合的函数divide,将10^5以上的数进行分解只需判断是否存在10^5以下的因数并分离即可加入son集合如果source已经小于10000说明已经可以按照80分代码逻辑处理。
multisetint divide(LL source)
{multisetint son;for(int j 2; j 10001;){if(source 10000){son.insert(source);break;}if(source % j 0){source source / j;son.insert(j);//cout j endl;continue;}j;}return son;
} 封装80分代码处理10^4以内数据的流程为无返回值函数cal。除了更换变量名称外需要注意80分代码可以丢掉小于阈值的指数100分代码则不行80分代码在处理到最后发现没有100以上质因数后直接丢掉剩下的质数而100分代码需要保留剩下的质数。 因为son集合其他成员分离出来的相同质因数的质数可以叠加。比如说102981488 23*46^4); 如果在处理23时认为质因数23的质数小于1后丢掉这个指数1就不能和后面46^4叠加了。
void cal(int num)
{for(int j 0; j 27;){if(num 1)break;if(num % (arr[j]) 0){num num / arr[j];longtp[arr[j]];continue;} //这里不需要判断指数是否大于阈值j;if(j 27)longtp[num]; //最后剩下的大于100的质数不能扔}
} 由此计算输出需要统一放到最后进行一次读取所有指数并进行相应乘法运算。
multisetint division;
division divide(n); //分离后的因式
memset(longtp, 0, sizeof(int)*10002); //每次都要初始化所有指数为0
for(auto it division.begin(); it ! division.end(); it)
{cal(*it); //计算所有因式
}
for(int j 2; j 10001; j) //统一判断阈值
{if(longtp[j] k)output * pow(j, longtp[j]);
}
完整代码如下
#include iostream
#include math.h
#include algorithm
#include string.h
#include setusing namespace std;typedef long long LL;
int longtp[10002];
int arr[27] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,87,93,97,101};multisetint divide(LL source)
{multisetint son;for(int j 2; j 10001;){if(source 10000){son.insert(source);break;}if(source % j 0){source source / j;son.insert(j);continue;}j;}return son;
}void cal(int num)
{for(int j 0; j 27;){if(num 1)break;if(num % (arr[j]) 0){num num / arr[j];longtp[arr[j]];continue;} //这里不需要判断指数是否大于阈值j;if(j 27)longtp[num]; //最后剩下的大于100的质数不能扔}
}int main()
{int q, k;LL n, output;int temp[102];cin q;for(int i 0; i q; i){output 1;cin n k;if(n 10000){multisetint division; //分离后的因式division divide(n);memset(longtp, 0, sizeof(int)*10002); //每次都要初始化所有指数为0for(auto it division.begin(); it ! division.end(); it)cal(*it); //计算所有因式for(int j 2; j 10001; j) //统一判断阈值if(longtp[j] k)output * pow(j, longtp[j]);}else{memset(temp, 0, sizeof(int)*102);for(int j 0; j 27; ){if(n % (arr[j]) 0){n n / arr[j];temp[arr[j]];continue;}if(temp[arr[j]] k)output * pow(arr[j], temp[arr[j]]);if(n 1)break;j;}}cout output endl;}return 0;
}
