在易语言里面做网站,php网站开发培训学校,中国工程局人才招聘网,网站购物车实现题干#xff1a;
七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧! 人们纷纷来到告示前,都想知道谁才是自己的另一半.告示如下: 数字N的因子就是所有比N小又能被N整除的…题干
七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧! 人们纷纷来到告示前,都想知道谁才是自己的另一半.告示如下: 数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6. 你想知道你的另一半吗?
Input
输入数据的第一行是一个数字T(1T500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1N500000).
Output
对于每组测试数据,请输出一个代表输入数据N的另一半的编号.
Sample Input
3
2
10
20
Sample Output
1
8
22
解题报告 约数和可以打表可以直接算。
AC代码1打表93ms打表的i那层循环到500000/2则78ms
#includebits/stdc.husing namespace std;
int num[500000 5],n;
int main()
{for(int i 1; i500000; i) {for(int j 2*i; j500000; ji) {num[j] i;}}int t; cint;while(t--) {scanf(%d,n);printf(%d\n,num[n]);}return 0 ;}
AC代码2不打表Tsqrtn的复杂度296ms
#include bits/stdc.h
#define ll long long
using namespace std;
const int MAX 1e510;
int p[MAX];
int a[MAX];
ll qpow(ll a,ll b) {ll ans 1;while(b){if(b 1) ans * a;b 1;a * a;}return ans;
}
int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);int cnt 0;int tmp n;// memset(a,0,sizeof a);for(int i 2; i * i n; i) {if(tmp % i 0) {p[cnt] i;a[cnt]0 ; while(tmp % i 0) {a[cnt];tmp / i;}}}if(tmp ! 1) {p[cnt] tmp;a[cnt] 1;}ll ans 1;for(int i 1; icnt; i) {ans * (qpow(p[i],a[i]1) - 1) / (p[i]-1);}printf(%lld\n,ans-n);//因为最后要输出的是除去自己的因为是因子因子不包括自己。 }return 0;
}
总结 这题你如果对a数组进行直接memset那恭喜你超时了。 因为T太大了,不能直接memset只能初始化到sqrt才可以。这是比较坑的一个地方。
附Tsqrt分解素数时的另一种简洁做法省掉一个数组
void getprimefactor(long long n) { //计算幂次方int cas0;for(int i0; ilenprime[i]*prime[i]n; i) {while(n%prime[i]0) { //可以整除factor[cas];n/prime[i];}if(factor[cas] ! 0)//就是进入了while里面的cas;}if(n1)factor[cas]1; //就是因为上面for条件的原因prime[i]*prime[i]n当不满足这个条件的时候就应该还有一个素数的一次方
}
