HDu 1286(オーラ関数phi)
2488 ワード
タイトル:
新しい友達を探す
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1882 Accepted Submission(s): 903
Problem Description
新年はもうすぐ着いて、“ブタの頭は協会を手伝います”は1つのパーティーをするつもりで、すでに既存の会員のN人を知っていて、会員を1からNまで番号をつけて、その中の会長の番号はN番で、会長と古い友达で、それではこの会員の番号はきっとNと1より大きい公約数があって、さもなくばすべて新しい友达で、今会長はいったい何人の新しい友达がいることを知りたいですか?プログラムを作って会長の計算を手伝ってください.
Input
1行目は、テストデータのグループ数CN(Case number,1
Output
Nごとに、新しい友达の人数を出力し、CN行の出力を共有します.
Sample Input
Sample Output
1つの数より小さいすべての互質数を求めることを意味し、オーラ式で互質数を求める.φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)
nは1から32768に遍歴し、各nと32768以下のすべての倍数を遍歴し、オーラ式に従って配列内の数値を更新する.n遍歴が完了すると求めたすべての数を表にします......直接出力すればいいです......
##コードは以下の通り
新しい友達を探す
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1882 Accepted Submission(s): 903
Problem Description
新年はもうすぐ着いて、“ブタの頭は協会を手伝います”は1つのパーティーをするつもりで、すでに既存の会員のN人を知っていて、会員を1からNまで番号をつけて、その中の会長の番号はN番で、会長と古い友达で、それではこの会員の番号はきっとNと1より大きい公約数があって、さもなくばすべて新しい友达で、今会長はいったい何人の新しい友达がいることを知りたいですか?プログラムを作って会長の計算を手伝ってください.
Input
1行目は、テストデータのグループ数CN(Case number,1
Output
Nごとに、新しい友达の人数を出力し、CN行の出力を共有します.
Sample Input
2
25608
24027Sample Output
7680
160161つの数より小さいすべての互質数を求めることを意味し、オーラ式で互質数を求める.φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)
nは1から32768に遍歴し、各nと32768以下のすべての倍数を遍歴し、オーラ式に従って配列内の数値を更新する.n遍歴が完了すると求めたすべての数を表にします......直接出力すればいいです......
##コードは以下の通り
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
const double EPS = 1e-10;
//
const int prime_num = 32768;
int prime[prime_num], cnt;
void init(){
memset(prime, 0, sizeof(prime));
for(int i = 2; i < prime_num; i ++){
if( prime[i] ) continue;
for(int j = i*i; j < prime_num; j += i) prime[j] = 1;
}
cnt = 0;
for(int i = 2; i < prime_num; i ++){
if( !prime[i] ) prime[cnt++] = i;
}
}
// phi()
int phi(int x){
int res = x;
for(int i = 0; i < cnt && prime[i] <= x; i ++) if( x % prime[i] == 0) res /= prime[i], res *= (prime[i] - 1);
return res;
}
int main(){
#ifndef in
ios::sync_with_stdio(false);
#endif
init();
int t, n;
cin >> t;
while(t--){
cin >> n;
int x = *lower_bound(prime, prime+cnt, n);
if( x == n) cout << n-1 << endl;
else cout << phi(n) << endl;
}
return 0;
}