hdu1164 Eddy's research I(数论:唯一分解式)

本文主要是介绍hdu1164 Eddy's research I(数论:唯一分解式)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一道很简单的水题有木有啊!!

我又TLE了好几次

原因是我用的是逗号表达式,今天听学长说了才知道,逗号表达式的结果就是最后一个逗号后表达式的结果

所以我的程序会一直判断正确,一直继续执行...

看到题目想都没想就用欧拉函数变形,TLE后我还以为真的是算法问题

想了想和打表差的也不多啊...

欧拉定理15ms:

#include <math.h>
#include <stdio.h>
#define MAXN 10010
int ans[MAXN];
int m, n, cnt, i;void euler_phi(int n) {m = sqrt(n+0.5);cnt = 0;for(i=2; i<=m; ++i) {if(n%i == 0) {n /= i;ans[cnt++] = i;while(n % i == 0) {n /= i;ans[cnt++] = i;}}}if(n > 1) ans[cnt++] = n;return ;
}int main(void) {while(scanf("%d", &n) != EOF) {euler_phi(n);printf("%d", ans[0]);for(i=1; i<cnt; ++i) {printf("*%d", ans[i]);}printf("\n");}return 0;
}

素数打表0ms:

#include <math.h>
#include <stdio.h>
#define MAXN 66010
int ans[20], prime[MAXN], vis[MAXN];
int m, n, cnt, i, j, c;void gen_primes(int n) {int m = (int)sqrt(n+0.5);for(i=2; i<=m; ++i) {if(!vis[i]) {for(j=i*i; j<=n; j+=i) {vis[j] = 1;}}}c = 0;for(i=2; i<=n; ++i) {if(!vis[i])prime[c++] = i;}return ;
}int main(void) {gen_primes(65536);while(scanf("%d", &n) != EOF) {cnt = 0;for(i=0; prime[i]<n; ++i) {j = prime[i];if(n%j == 0) {ans[cnt++] = j;n /= j;while(n%j == 0) {n /= j;ans[cnt++] = j;}}}if(n > 1)ans[cnt++] = n;printf("%d", ans[0]);for(i=1; i<cnt; ++i) {printf("*%d", ans[i]);}printf("\n");}return 0;
}

这篇关于hdu1164 Eddy's research I(数论:唯一分解式)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---