首页 > 代码库 > 巴蜀2904 MMT数
巴蜀2904 MMT数
Description
FF博士最近在研究MMT数。
如果对于一个数n,存在gcd(n,x)<>1并且n mod x<>0 那么x叫做n的MMT数,显然这样的数可以有无限个。
FF博士现在想知道在所有小于n的正整数里面有多少个n的MMT数。
如果对于一个数n,存在gcd(n,x)<>1并且n mod x<>0 那么x叫做n的MMT数,显然这样的数可以有无限个。
FF博士现在想知道在所有小于n的正整数里面有多少个n的MMT数。
Input
仅一行一个数为n。
Output
输出所有小于n的正整数里面有多少个n的MMT数。
Sample Input
10
Sample Output
3
Hint
【样例解释】
3个数分别是 4 6 8,gcd(n,x)的意思是求n和x的最大公约数。
【数据范围】
对于50%的数据 n<=1000000
对于100%的数据n<=maxlongint
3个数分别是 4 6 8,gcd(n,x)的意思是求n和x的最大公约数。
【数据范围】
对于50%的数据 n<=1000000
对于100%的数据n<=maxlongint
Source
xinyue
总数减去欧拉函数,再减去因数的数量,再加上被多减了一次的1,就是答案。
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 int n,m; 9 int solve(int x){10 int res=x;//欧拉函数11 int cnt=1;//因数12 for(int i=2;i*i<n;i++){13 if(x%i)continue;14 res=res/i*(i-1);15 int c=0;16 while(x%i==0){17 x/=i;18 c++;19 }20 cnt*=c+1;21 }22 if(x>1){23 cnt*=2;24 res=res/x*(x-1);25 }26 return res+cnt;27 }28 int main(){29 scanf("%d",&n);30 solve(n);31 printf("%d\n",n-solve(n)+1);32 return 0;33 }
巴蜀2904 MMT数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。