全部博文  (当前页7篇, 共208篇)

Min_25筛(EES筛)法

## Extended Eratosthenes Sieve [参考链接](https://www.spoj.com/problems/TEES/tdsourcetag=s_pctim_aiomsg) 给出一个积性函数(一些非积性函数也可以搞一搞)$f$,且$f(p)$为关于$p$的多项式。求$S(n)=\sum_{i=1}^nf(i)$ $\forall \ 2\le i\le ...

HYSBZ - 2818

##problem 给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对. N1e7 ##思路 枚举素数(大概几e5个) 对于每个素数暴力算(先预处理筛出欧拉值) 时间复杂度 $case*O(素数个数)$ ##代码示例 ``` #include using namespace std; typedef long long ll; const int ...

18四川省赛G题 分段 数论函数

## problem 计算 $$ ans =\sum^n_{i=1}\sum^i_{j=1} (n\ mod (i \times j)) $$ $1 ≤ n ≤ 10^{11}$ ## 思路 **解法一** 首先写作$\sum^n_{i=1}\sum^i_{j=1} (n-\left \lfloor \frac{n}{ij} \right \rfloor*ij)=\sum^n_...

CF757E(积性函数)

##problem ![img](https://s1.ax2x.com/2018/09/05/5BqJCy.png) ##思路 满足$pq=n$且$gcd(p,q)=1$的二元组个数是多少呢? 显然是$2^{w(n)}$个,其中$w(n)$是不同的素因子的数目 那么$f_{r+1}(n)=\sum_{uv=n}\frac{f_r(u)+f_r(v)}{2}$如何计算呢? $f...

HDU5528 积性函数

## HDU 5528 Marry likes to count the number of ways to choose two non-negative integers aa and bbless than mm to make a×ba×b mod m≠0m≠0. Let's denote f(m)f(m) as the number of ways to choose tw...

bzoj 2705

Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。 ##Input 一个整数,为N。 ##Output 一个整数,为所求的答案。 ##Sample Input 6 ##Sample Output 15 ##Hint 【数据范围】 对于60%的数据,0 #include #include u...

51nod 1060 (因子最多数)

## 因子个数最多的数 实际上,这样的数称为反素数: ![img](https://s1.ax2x.com/2018/09/03/5Bl6ky.png) 即给定$N$,求$[1,N]$之间最大的反素数**(即拥有因子数目最多的数)** 性质: > No.1 一个反素数的质因子必然是从2开始连续的质数。 > No.2 p=2^t1 x 3^t2 x 5^t3 x 7^t4….....

当前第4页,共30页