caioj 1158 欧拉函数

直接套模板，这道题貌似单独求还快一些

解法一

#include<cstdio> #include<cctype> #define REP(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std;typedef long long ll; const int MAXN = 21234567; int euler[MAXN];void get_euler() {_for(i, 1, MAXN) euler[i] = i;_for(i, 2, MAXN)if(euler[i] == i)for(int j = i; j <= MAXN; j += i)euler[j] = euler[j] / i * (i - 1); }void read(ll& x) {int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f; }int main() {get_euler();ll n, x; read(n);while(n--){read(x);printf("%lld\n", euler[x]);}return 0; }

解法二

#include<cstdio> #include<cctype> #define REP(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std;typedef long long ll; const int MAXN = 21234567;ll euler(ll x) {ll ret = x;for(int i = 2; i * i <= x; i++)if(x % i == 0){ret = ret / i * (i - 1);while(x % i == 0) x /= i;if(x == 1) break;}if(x > 1) ret = ret / x * (x - 1);return ret; }void read(ll& x) {int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f; }int main() {ll n, x; read(n);while(n--){read(x);printf("%lld\n", euler(x));}return 0; }

 

转载于:https://www.cnblogs.com/sugewud/p/9819359.html

总结

以上是生活随笔为你收集整理的caioj 1158 欧拉函数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。