题目

次方

hdu2204

求[1,N]中可以表示为$M^K$的数的个数,K>1。
若$M^K \le N \; , \; 那么,i^K \le N (i < M)$,那么就表示可以表示为K次方的数有M个。
我们发现不同的K肯定互质,比如,$4^2$ 和 $2^4$ 就重复表示了。
因为$2^{60} > 10^{18},2*3*5*7>60$,所以这里的K最多表示为3个60以内不同素数的乘积。
最后答案即
$$\sum|p_i| - \sum|p_ip_j| + \sum|p_ip_jp_k|$$

另外需要注意开方的精度问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<cmath>

typedef long long LL;
const double eps = 1e-8;
const int maxn = 65;
int primes[maxn],tot;
bool vis[maxn];
LL ans,n;

void init()
{
tot = 0;
memset(vis,0,sizeof vis);
for(int i=2;i<maxn;++i)
{
if(!vis[i])
{
primes[tot++] = i;
for(int j=i+i;j<maxn;j+=i) vis[j] = 1;
}
}
}

void dfs(int k,int cur,int st)
{
for(int i=st;i<tot;++i)
{
int num = (int)(pow(n,1.0/(cur*primes[i]))+eps);
if(k&1)
ans+= num;
else
ans-= num;
if(num == 1) break;
dfs(k+1,cur*primes[i],i+1);
}
}

int main()
{
//freopen("test.txt","r",stdin);
init();
while(scanf("%lld",&n)==1)
{
ans = 0;
dfs(1,1,0);
printf("%lld\n",ans);
}
return 0;
}

整除与互质

hdu4135

求[a,b]中与n互质的数的个数
我们知道[1,m]中能被$p_i$整除的个数为$\lfloor \frac{m}{p_i} \rfloor$
那么[1,m]中与n互质的数的个数即 $m - \sum_{能被n整除} 1$
$$\sum_{能被n整除} 1 = \sum_{能被p_i整除} 1 - \sum_{能被p_i 和 p_j 整除} 1 + \sum_{能被p_i 和 p_j 和 p_k 整除} 1 - … $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

typedef long long LL;

int n,sz;
vector<int> fac;

void init()
{
fac.clear();
int t = n , m = (int)sqrt(n+0.5);
for(int i=2; i<=m ;++i)
{
if(t%i == 0)
{
fac.push_back(i);
while(t%i == 0)
{
t/=i;
}
}
if(t == 1) break;
}
if(t>1) fac.push_back(t);
sz = fac.size();
// for(int i=0;i<fac.size();++i) printf("%d\n",fac[i]);
}

LL solve(LL r)
{
LL sum = 0;
for(int i=1;i<(1<<sz);++i)
{
int cnt = 0,mul = 1;
LL res = 0;
for(int j=0;j<sz;++j)
{
if(i&(1<<j))
{
mul *= fac[j];
++cnt;
}
}
if(cnt&1)
sum += r/mul;
else
sum -= r/mul;
}
return r - sum;
}

int main()
{
//freopen("test.txt","r",stdin);
int T;
scanf("%d",&T);
for(int z=1;z<=T;++z)
{
LL a,b;
scanf("%lld %lld %d",&a,&b,&n);
init();
printf("Case #%d: %lld\n",z,solve(b) - solve(a-1));
}
return 0;
}

hdu1796

求[a,b]中至少能被m个元素的集合s中的一个数整除的数的个数
与上面类似,只不过这里枚举的是不同个元素的lcm

参考