莫比乌斯反演 - hzwer.com

「CF235X」Codeforces Round #146 (Div. 1)
A.LCMChallenge显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下[crayon-6767e34d90242043118142/]B.Let'sPlayOsu!计算出到每个位置的期望连续长度就可以得到如果该位置正确的期望得分，就可以dp辣[crayon-6767e34d9024e720111461/]C.CyclicalQuest一道很正经的后缀自动机建出s串的后缀自动机把xi复制一遍接在后面，然后在s串上匹配，就可以得出后缀自动机上贡献答案的结点[crayon-6767e34d9...
02015年6月15日7,559深度搜索,广度搜索,后缀自动机,概率与期望,莫比乌斯反演

「JoyOI」五月有奖赛暨Loi 55 Round #1 Day1
题解http://pan.baidu.com/s/1bnjO0ij选择题（byDarkfalmes）[crayon-6767e34d91425237286104/]王的对决！(byrainheart&seavot)[crayon-6767e34d91430329822375/]dC的肥皂（byskyfall（Orz））60暴力[crayon-6767e34d91436432025463/]DQS和序列（by帝江&Darkfalmes）[crayon-6767e34d9143d985136852/] ...
22015年4月30日4,055递推与动规,线段树,广度搜索,筛法,莫比乌斯反演
「BZOJ2154」Crash的数字表格
Description今天的数学课上，Crash小朋友学习了最小公倍数(LeastCommonMultiple)。对于两个正整数a和b，LCM(a,b)表示能同时被a和b整除的最小正整数。例如，LCM(6,8)=24。回到家后，Crash还在想着课上学的东西，为了研究最小公倍数，他画了一张N*M的表格。每个格子里写了一个数字，其中第i行第j列的那个格子里写着数为LCM(i,j)。一个4*5的表格如下：1234522641036312154412420看着这个表格，Crash想到了很多可以思...
22015年4月24日6,475莫比乌斯反演
「BZOJ3529」[SDOI2014] 数表
Description 有一张N×m的数表，其第i行第j列（1<=i<=礼，1<=j<=m）的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。Input 输入包含多组数据。输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a|<=10^9)描述一组数据。Output 对每组数据，输出一行一个整数，表示答案模2^31的值。SampleInput244310105SampleOutput20148HIN...
22015年1月13日7,286莫比乌斯反演
「BZOJ2820」YY的GCD
Description神犇YY虐完数论后给傻×kAc出了一题给定N,M,求1<=x<=N,1<=y<=M且gcd(x,y)为质数的(x,y)有多少对kAc这种傻×必然不会了，于是向你来请教……多组输入Input第一行一个整数T表述数据组数接下来T行，每行两个正整数，表示N,MOutputT行，每行一个整数表示第i组数据的结果SampleInput21010100100SampleOutput302791HINTT=10000N,M<=10000000Source 假定n<m\[\sum_{isprime(p)...
62015年1月12日9,632莫比乌斯反演
「BZOJ2440」[中山市选2011] 完全平方数
Description小X自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。这天是小X的生日，小W想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第K个数送给了小X。小X很开心地收下了。然而现在小W却记不起送给小X的是哪个数了。你能帮他一下吗？Input包...
02014年10月25日6,634莫比乌斯反演
「vijos1889」天真的因数分解
描述小岛:什么叫做因数分解呢?doc:就是将给定的正整数n,分解为若干个素数连乘的形式.小岛:那比如说n=12呢?doc:那么就是12=2X2X3呀.小岛:呜呜,好难,居然素数会重复出现,如果分解后每一个素数都只出现一次,我就会.wish:这样来说,小岛可以正确分解的数字不多呀.doc:是呀是呀.wish:现在问题来了,对于给定的k,第k个小岛无法正确分解的数字是多少?格式输入格式输入只有一行,只有一个整数k.输出格式输出只有一行,只有一个整数,表示小岛无...
02014年10月25日4,750莫比乌斯反演
「BZOJ2301」[HAOI2011] Problem b
Description对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y)=k，gcd(x,y)函数为x和y的最大公约数。Input第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、kOutput共n行，每行一个整数表示满足要求的数对(x,y)的个数SampleInput22515115152SampleOutput143HINT100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000题解同bzoj1101TT就是区间加加减减...
02014年9月1日7,174莫比乌斯反演
「BZOJ1101」[POI2007] Zap
$「BZOJ1101」[POI2007] Zap$
DescriptionFGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。Input第一行包含一个正整数n，表示一共有n组询问。（1<=n<=50000）接下来n行，每行表示一个询问，每行三个正整数，分别为a,b,d。（1<=d<=a,b<=50000）Output对于每组询问，输出到输出文件zap.out一个正整数，表示满足...
32014年9月1日9,417莫比乌斯反演