首页 > 代码库 > poj 1091 跳骚
poj 1091 跳骚
1 /** 2 题意: 求对于小于m的n个数, 求x1*a1 + x2*a2+x3*a3........+xn*an = 1 3 即求 a1,a2,a3,。。。。an 的最大公约数为1 , a1,a2....an 可重复 4 原理 : 容斥原理 所有的 排序即 m^n ——不符合的情况 ,即为所求 5 不符合的情况: 就是 这n个数有最大公约数 不是1, 即这n个数是m 的素因子的组合。。 6 一共有 m^n张卡片,如果减去其中含有公约数的卡片剩下的就是所求的结果 7 举个例子 n=2, m=360; 360=2^3*3^2*5 8 案 = (m ^ n) - (有公因数2的n元组)- (有公因数3的n元组)- (有公因数5的n元组)+ (有公因数2,3的n元组) +(有公因数2,5的n元组) + (有公因数3,5的n元组)- (有公因数2,3,5的n元组)。 9 特殊之处: m^n - (m/2)^n-(m/3)^n........+ (m/2*3)^n+ (m/2*5)^n......-(m/2*3*5)^n 10 -------> m^n(1-1/2^n)(1-1/3^n)(1-1/5^n)...... 11 好像是叫扩展欧拉函数 12 13 **/ 14 #include <iostream> 15 #include <algorithm> 16 #include <cstdio> 17 using namespace std; 18 19 long long pow(long long a,long long b){ 20 long long c =1; 21 while(b){ 22 if(b&1) 23 c = c*a; 24 a =a*a; 25 b>>=1; 26 } 27 return c; 28 } 29 30 long long res(long long n,long long m){ 31 long long sm = pow(m,n); 32 long long ans = m; 33 long long temp ; 34 for(int i=2;i*i<=ans;i++)if(m%i==0){ 35 temp = pow(i,n); 36 sm = sm/temp*(temp-1); 37 while(m%i==0) m /= i; 38 } 39 if(m>1){ 40 temp = pow(m,n); 41 sm = sm/temp*(temp-1); 42 } 43 return sm; 44 45 } 46 int main() 47 { 48 long long n,m; 49 cin>>n>>m; 50 long long s = res(n,m); 51 cout<<s<<endl; 52 return 0; 53 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。