[Ahoi2005]COMMON 约数研究 【欧拉线性筛的应用】
1968: [Ahoi2005]COMMON 约数研究Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 2939 Solved: 2169[Submit][Status][Discuss]DescriptionInput只有一行一个整数 N（0 < ...
51nod 1237 最大公约数之和 V3【欧拉函数||莫比乌斯反演+杜教筛】
用mu写lcm那道卡常卡成狗(然而最后也没卡过去，于是写一下gcd冷静一下首先推一下式子\[\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\]\[\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d=1}^{n}[gcd(i,j)==d]d\]\[\sum...
51nod 1227 平均最小公倍数【欧拉函数+杜教筛】
以后这种题能用phi的就不要用mu…mu往往会带着个ln然后被卡常致死把题目要求转换为前缀和相减的形式，写出来大概是要求这样一个式子：\[\sum_{i=1}^{n}\sum_{j=1}^{i}\frac{j}{gcd(i,d)}\]注意j的限制是i\[\sum_{d=1}^{n}\sum_{i=1...
BZOJ4916 神犇和蒟蒻 【欧拉函数 + 杜教筛】
题目很久很久以前，有一只神犇叫yzy;很久很久之后，有一只蒟蒻叫lty;输入格式请你读入一个整数N;1<=N<=1E9,A、B模1E9+7;输出格式请你输出一个整数A=\sum_{i=1}^N{\mu (i^2)};请你输出一个整数B=\sum_{i=1}^N{\varphi (i^2)...
【luogu3768】简单的数学题 欧拉函数(欧拉反演)+杜教筛
题目描述给出 $n$ 和 $p$ ，求 $(\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j))\mod p$ 。$n\le 10^{10}$ 。题解欧拉函数(欧拉反演)+杜教筛推式子：$$\begin{align}&\sum\limits_{...
51Nod.1237.最大公约数之和 V3(莫比乌斯反演 杜教筛 欧拉函数)
题目链接\(Description\)\(n\leq 10^{10}\)，求\[\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\ mod\ (1e9+7)\]\(Solution\)首先\[\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)=\sum_{d=1}^nd...
BZOJ4916 神犇和蒟蒻（欧拉函数+杜教筛）
第一问是来搞笑的。由欧拉函数的计算公式容易发现φ(i2)=iφ(i)。那么可以发现φ(n2)*id(n)（此处为卷积）=Σd*φ(d)*(n/d)=nΣφ(d)=n2 。这样就有了杜教筛所要求的容易算前缀和的两个函数。一通套路即可。#include<iostream>#include&l...
51nod 1239 欧拉函数之和【欧拉函数+杜教筛】
和bzoj 3944比较像，但是时间卡的更死设\( f(n)=\sum_{d|n}\phi(d) g(n)=\sum_{i=1}^{n}f(i) s(n)=\sum_{i=1}^{n}\phi(i) \)，然后很显然对于mu\( g(n)=1\)，对于\( g(n)=n*(n+1)/2 \)，然后可...
bzoj 3944: Sum【莫比乌斯函数+欧拉函数+杜教筛】
一道杜教筛的板子题。两个都是积性函数，所以做法是一样的。以mu为例，设\( f(n)=\sum_{d|n}\mu(d) g(n)=\sum_{i=1}^{n}f(i) s(n)=\sum_{i=1}^{n}\mu(i) \)，然后很显然对于mu\( g(n)=1\)，对于phi\( g(n)=n*(...
Dirichlet's Theorem on Arithmetic Progressions POJ - 3006 线性欧拉筛
题意 给出a d n 给出数列 a,a+d,a+2d,a+3d......a+kd 问第n个数是几 保证答案不溢出直接线性筛模拟即可 #include<cstdio> #include<cstring> using namespace std; bool Is_Prim...
【51nod】1239 欧拉函数之和 杜教筛
【题意】给定n，求Σφ(i)，n<=10^10。【算法】杜教筛【题解】定义$s(n)=\sum_{i=1}^{n}\varphi(i)$杜教筛$\sum_{i=1}^{n}(\varphi *I)(i)=\sum_{i=1}^{n}\sum_{d|i}\varphi(d)=\sum_{i=1}...
【bzoj2401】陶陶的难题I “高精度”+欧拉函数+线性筛
题目描述求输入第一行包含一个正整数T，表示有T组测试数据。接下来T<=10^5行，每行给出一个正整数N,N<=10^6。输出包含T行，依次给出对应的答案。样例输入71101001000100001000001000000样例输出121271844622418301130466018271...
lightoj1370欧拉函数/素数筛
这题有两种解法，1是根据欧拉函数性质：素数的欧拉函数值=素数-1（可根据欧拉定义看出）欧拉函数定义：小于x且与x互质的数的个数#include<map>#include<set>#include<cmath>#include<queue>#includ...
Bi-shoe and Phi-shoe（欧拉函数/素筛）题解
Bi-shoeandPhi-shoeBambooPole-vaultisamassivelypopularsportinXzhiland.AndMasterPhi-shoeisaverypopularcoachforhissuccess.Heneedssomebamboosforhisstudent...
【bzoj2190】【仪仗队】欧拉函数+线性筛（浅尝ACM-J）
向大（hei）佬（e）*学（di）习（tou）Description作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N*N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。现在，C君希望你告诉他队伍整齐时能看到的...
BZOJ4804 欧拉心算（莫比乌斯反演+欧拉函数+线性筛）
一通套路后得Σφ(d)μ(D/d)⌊n/D⌋2。显然整除分块，问题在于怎么快速计算φ和μ的狄利克雷卷积。积性函数的卷积还是积性函数，那么线性筛即可。因为μ(pc)=0(c>=2)，所以f(pc)还是比较好算的，讨论一波即可。#include<iostream>#include<...
bzoj 2005: [Noi2010]能量采集 筛法||欧拉||莫比乌斯
2005:[Noi2010]能量采集TimeLimit: 10Sec MemoryLimit: 552MB[Submit][Status][Discuss]Description栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇...
Bzoj 2818: Gcd 莫比乌斯,分块,欧拉函数,线性筛
2818:GcdTimeLimit: 10Sec MemoryLimit: 256MBSubmit: 3241 Solved: 1437[Submit][Status][Discuss]Description给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多...
HDU6434 Count【欧拉函数 线性筛】
HDU6434I.CountT次询问，每次询问\(\sum_{i=1}^{n}\sum_{j=1}^{n-1}[gcd(i-j,i+j)=1]\)\(T\le1e5,n\le2e7\)对原式进行转换，枚举\(i-j\)，\(i-j\)为\(j\) ，那么可以变换为\(\sum_{i=1}^{n}\s...
Farey Sequence （素筛欧拉函数/水）题解
TheFareySequenceFnforanyintegernwithn>=2isthesetofirreduciblerationalnumbersa/bwith0<a<b<=nandgcd(a,b)=1arrangedinincreasingorder.Thefirst...