UESTC 618 无平方因子数 (容斥 + 莫比乌斯反演)

2024-03-20 13:58

本文主要是介绍UESTC 618 无平方因子数 (容斥 + 莫比乌斯反演),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

无平方因子数

Time Limit: 4000/2000MS (Java/Others)   

Memory Limit: 65535/65535KB (Java/Others)


Submit  Status
无平方因子数即对于任意一个素数p,p2都不会整除那个数,如1 , 5=5 , 15=3×5都是无平方因子数,而20=22×5不是。现在给定一个n (1≤n<1012) ,求区间[1,n]中无平方因子数的个数。

Input
第一行有个整数T,代表数据组数(T≤10)

接下来有T行,每行有个整数n (1≤n<1012)

Output
输出T行,每行输出一个整数代表区间[1,n]内的无平方因子数的个数。

Sample Input   
3
1
10

30

Sample Output

1
7

19


Source

UESTC Training for Math


题目链接:http://acm.uestc.edu.cn/#/problem/show/618

题目分析:又是无平方因子数,比BZOJ那题简单很多,直接算就行了,参照BZOJ 2440

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const MAX = 1e6 + 5;
int mob[MAX], p[MAX];
bool prime[MAX];void Mobius()
{int pnum = 0;memset(prime, true, sizeof(prime));mob[1] = 1;for(int i = 2; i < MAX; i++){if(prime[i]){p[pnum ++] = i;mob[i] = -1;}for(int j = 0; j < pnum && i * p[j] < MAX; j++){prime[i * p[j]] = false;if(i % p[j] == 0){mob[i * p[j]] = 0;break;}mob[i * p[j]] = -mob[i];}}
}ll cal(ll n)
{ll cnt = 0;for(ll i = 1; i * i <= n; i++)cnt += (ll) mob[i] * (n / (i * i));return cnt;
}int main()
{Mobius();int T;scanf("%d", &T);while(T --){ll n;scanf("%lld", &n);printf("%lld\n", cal(n));}
}



这篇关于UESTC 618 无平方因子数 (容斥 + 莫比乌斯反演)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829670

相关文章

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

hdu4407容斥原理

题意: 有一个元素为 1~n 的数列{An},有2种操作(1000次): 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

hdu6053 TrickGCD 莫比乌斯反演

TrickGCD Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Problem Description You are given an array  A  , and Zhu wants to know there are how many d

容斥问题

一、填空题 1.一个班有45个小学生,统计借课外书的情况是:全班学生都借有语文或数学课外书.借语文课外书的有39人,借数学课外书的有32人.语文、数学两种课外书都借的有     人. 3.在1~100的自然数中,是5的倍数或是7的倍数的数有     个. 4.某区100个外语教师懂英语或俄语,其中懂英语的75人,既懂英语又懂俄语的20人,那么懂俄语的教师为     人. 5.六一班

HDU2521(求因子个数)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2521 解题思路: 数据量不大,直接O(n)遍历,对每个数求其因子个数,找出最大的即可。 完整代码: #include <functional>#include <algorithm>#include <iostream>#include <fstream>#includ

连分数因子分解法——C语言实现

参考网址:连分数分解法寻找整数的因子(Python)-CSDN博客 大数运算:C语言实现 大数运算 加减乘除模运算 超详细_64编程 加减乘除取模 复杂运算-CSDN博客 ‌连分数因子分解法‌是一种用于大整数因子分解的算法,它是计算数论中的一个重要方法。连分数因子分解法通过寻找x2≡y2 (mod p)x2≡y2 (mod p)的形式来分解N。具体来说,这种方法涉及到计算N的简单连分数展开,并

js算法题,给任意一个偶数,找出他的所有的质数因子

/*给任意一个偶数,找出他的所有的质数因子*/ function primeFactor(n){     var factors=[],            divistor=2;     if(typeof n !=='number'||!Number.isInteger(n)){          return 0;     }; //如果不是偶数返回0,如果是0,返回0

【HDU】2204 Eddy's爱好 容斥原理

传送门:【HDU】2204 Eddy's爱好 题目分析:首先,对于所有形如M^K的数我们都可以转化成M^(p1^k1 * p2^k2 * p3^k3 * ... )的形式,其中p1,p2,p3..为素数。则所有的M^K都可以转化成M'^p,其中p为素数。我们意识到2^60>10^18,所以只要求出前60以内的所有素数即可。然后,由于2*3*5*7>60,其中一个K的质因数最多只有三种。