xumOJ 1447 积性函数
[cpp]/*
xmu 1447 积性函数
题解：当 (a,b)=1; 则 f(a*b)=f(a)*f(b);
x[i] 表示欧拉函数
sum[i] 表示因子个数
p[i] 表示第 i 个素数
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define manx 1000001
using namespace std;
int x[manx],sum[manx],p[manx];
bool s[manx];
void prime(){
int num=0;
for(int i=0;i<manx;i++) s[i]=0,x[i]=0,sum[i]=1,p[i]=0;
for(int i=2;i*i<manx;i++){
if(!s[i]){
p[num++]=i;
for(int j=2;j*i<manx;j++)
s[i*j]=1;
}
}
for(int i=2;i<manx;i++)
if(!s[i]) p[num++]=i;
}
void oula(){
for(int i=2; i<manx;i++){
if(!s[i]){
x[i]=i-1;
sum[i]=2;
continue;
}
for(int j=0;p[j]*p[j]<=i;j++){
if(i%p[j]==0){
if(i/p[j]%p[j]){ ////只有一个p[j]素数因子
sum[i]=sum[i/p[j]]*2;
x[i]=x[i/p[j]]*x[p[j]];
}
else { ////////可能有多个 p[i]的素数因子
int ans = i;
x[i]=x[i/p[j]]*p[j];
while(ans%p[j]==0) ans/=p[j]; ///明白这段还是需要组合数学知识的
sum[i]=sum[ans]+sum[i/p[j]]; ///更新 i 的因子个数
}
break; ///// 处理完跳出循环
}
}
}
}
int main(){
prime();
oula();
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",n-sum[n]-x[n]+1);
}
}
补充：软件开发 , C++ ,
