电子科技大学 无平方因子数
Description
无平方因子数即对于任意一个素数p,p^2都不会整除那个数,如1 , 5=5 , 15=3*5都是无平方因子数,而20=2^2*5不是。现在给定一个n (1 <= n < 10^12),求区间[1,n]中无平方因子数的个数。
Input
第一行有个整数T,代表数据组数(T <= 10)
接下来有T行,每行有个整数n (1 <= n < 10^12)
Output
输出T行,每行输出一个整数代表区间[1,n]内的无平方因子数的个数。
Sample Input
3
1
10
30
Sample Output
1
7
19
这道题是在白书上看到的,但是白书上介绍的算法是用类素数筛法的方法解决。但是这里的数据太大了,显然是不能够解决的。于是要领想他法,后来才发现这是可以用离散数学里的包含排斥原理。就是数论中的容斥原理。
本人表示刚学过离散,所以这里就以课本里的包含排斥原理给大家讲解如何解该道题把.
直接给出离散书中的公式吧:
S- |Pi|(1<= i <= n)+|Pi&&Pj|(1<=i < j<= n)-......+(-1)^n|Pi &&Pj&&.....Pn|
其中公式的意思是,表示事件Pi发生,Pi&&Pj表示事件Pi和事件Pj同时发生。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
const int N = 1e6 + 5;
int top,prime[N];
void IsPrime()
{
bool vst[N];
memset(vst,0,sizeof(vst));
for(int i = 2;i < N;++i)if(!vst[i])
{
prime[top++] = i;
for(int j = i+i;j < N;j += i)
vst[j] = 1;
}
}
LL Solve(int r,LL num)
{
LL res = 0;
for(int i=r;(i<top)&&(LL)prime[i]*prime[i]<=num;++i)
{
//LL tmp = prime[i]*prime[i];
res += num/prime[i]/prime[i] - Solve(i+1,num/prime[i]/prime[i]);// S - |Ai|(1<=i<=n) + |Ai&&Aj|(1<=i<j<=n)-...
}
return res;
}
int main()
{
IsPrime(); //cout<<top<<endl;
int T;
LL n;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
printf("%lld\n",n-Solve(0,n));
}
return 0;
}
M^k数 || HDU 2204 Eddy's爱好
时间限制:1000ms | 内存限制:65535KB
难度:4
描述
给你一个数n,请算出1~n之间有多少个整数能表示为M^k(k>1,m,k都是正整数)形式的个数。
输入
每行一个整数n(1<=n<=10^18)。
输出
输出1~n符合条件的数的个数。
样例输入
4
36
1000000000000000000
样例输出
2
9
1001003332
幸好在离散里,自己偷学了包含排斥公式,因此看到的时候不会一头雾水。
题目分析:
既然是中文就没有什么可解释的了。自己看吧。
思路分析:
我们可以从题目给出的数据看到,n的范围是64位的,而不像电子科技大学的那到题一样可以打表过。因为当1*10^8的时候素数已经到达了1*10^7显然是TEL。所以,要另想他法。最后。。。。。我是没想到可以用包容排斥原理,是偷看了别人的博客才知道的,囧!!因为,这道题涉及了一个我还没学过的数学知识。下面就讲一下该题主要涉及了那些知识吧。
1.一个数的x = n^(1/p)表示n中有x个p次方组成。
2.任意一个数n可以表示成由n^P组成的形式。
求解过程,我们可以根据上一题给出的包含排斥原理,来算出结果。先算出一个素数的情况,然后是两个,最后是三个,因为
2*3*5 = 60 ,而2^60 > 10^18所以只要算到三个素数的情况就好了。
#include <stdio.h>
#include <math.h>
typedef long long LL;
const double EPS = 1e-8;
const int prime[20] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
int main()
{
// printf("%lf\n",EPS);
LL n;
while(~scanf("%lld",&n))
{
int i,j,k,ans = 1;
LL tmp;
for(i = 0;i <= 16;i++)
{
tmp = (long long)(pow(double(n),(1.0/(1.0*prime[i])))+EPS);
if(tmp == 1)break;
ans += tmp - 1;
}
for(i = 0;i <= 16;++i)
for(j = i+1;j <= 16;++j)
{
tmp = (long long)(pow(double(n),(1.0/(1.0*prime[j]*prime[i])))+EPS);
if(tmp == 1) break;
ans -= tmp - 1;
}
for(i = 0;i <= 16;++i)
for(j = i+1;j <= 16;++j)
for(k = j+1;k <= 16;++k)
{
tmp = (long long)(pow(double(n),(1.0/(1.0*prime[i]*prime[j]*prime[k])))+EPS);
if(tmp == 1) break;
ans += tmp - 1;
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
重点介绍鸽巢原理的应用,在组合数学中鸽巢原理的定义及其主要应用
第四版组合数学习题答案 第四版组合数学习题答案 挺有用的第四版组合数学习题答案 第四版组合数学习题答案 挺有用的第四版组合数学习题答案 第四版组合数学习题答案 挺有用的第四版组合数学习题答案 第四版组合数学...
组合数学组合数学组合数学组合数学
组合数学期末课程论文总结,详细讲述了组合数学的核心内容以及发展史
Richard组合数学答案Richard组合数学答案Richard组合数学答案Richard组合数学答案Richard组合数学答案Richard组合数学答案Richard组合数学答案Richard组合数学答案Richard组合数学答案
组合数学习题答案组合数学习题答案组合数学习题答案
组合数学 抽屉原理 奥林匹克竞赛试题.
组合数学习题答案组合数学习题答案组合数学习题答案
组合数学具有悠久的历史。但是,它的发展壮大还是近几十年的事情,特别是计算机的问世以及计算机的广泛应用,促使了组合数学的蓬勃发展;反过来,由于组合数学的发展.又推动了计算机科学日新月异的进步。 同样...
组合公式的一个新证法 组合公式的一个新证法 组合公式的一个新证法 组合公式的一个新证法
组合数学基本原理(陈景润)组合数学基本原理(陈景润)
\数论、组合数学、具体数学\数论、组合数学、具体数学\数论、组合数学、具体数学\数论、组合数学、具体数学
这个PPT的内容是组合数学的鸽巢原理。 可以用来学习等。 让你懂得鸽巢原理。
中科大组合数学习题答案,狭义的组合数学主要研究满足一定条件的组态(也称组合模型)的存在、计数以及构造等方面的问题。 组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化(最佳组合)等
1.1 组合数学研究的对象 1.2 组合问题典型实例 1.2.1 分派问题 1. 2.2 染色问题 1.2.3 幻方问题 1.2.4 36军官问题 1.2.5 中国邮路问题 习 题 第二章 排列与组合 2.1 两个基本计数原理 2.2 无...
组合数学领域 Catalan数的应用研究 吉林大学软件学院 1.卡特兰数简介 卡特兰数(Catalan Number)是组合数学中应用广泛的重要计数函数,以比利时的数学家欧仁·查理·卡塔兰(1814–1894)的名字来命名,其前几项为...
组合数学入门书籍,中国科学技术大学的组合数学引论课指定教材。
它是组合数学中一个重要的原理。抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。”
组合数学中文翻译版。由山东大学数学学院提供,Richard-A[1].Brualdi-组合数学习题解答