每天看一遍
1LL<<ll改回int\0$\varphi(n)$：$1$到$n$中与$n$互质的数的个数
$$
\varphi(n)=n\prod_{p|n}(1-{1\over p})
$$
其中$p$是$n$的素因子
关于这个公式的理解，可以先考虑只有一个素数因子的形式。
若$n=a^p$,则$[1,n]$中能被a整除的数分别为$a,2a,3a,…,a^{p-1}a$，共$a^{p-1}={n\over a}$个，剩下的是不能被$a$整除的数，自然的就和n互质。因此容易得到$\varphi(n)=n−{n\over a}=n(1−{1\over a})$
从上面的例子可以看出，a的倍数其实是在$[1,x]$之间平均分布的。这样的平均分布适用于任何的数的倍数。
当一个数有多个素数因子的时候，可以利用这些因子的倍数是各自平均分布的性质，依次累乘上$(1−{1\over p})$.相当于筛去了$p$的倍数。
举个例子：$30=2·3·5$
$1,2,3,4,5,6,7,8,9,10,……,28,29,30$
共30个数，先乘$(1−{1\over 2})$剩下了15个数：
$1,3,5,7,9,11,13,15,17,19,21,23,25,27,29$
再乘$(1−{1\over 3})$筛去了5个，剩下10个数：
1,5,7,11,13,17,19,23,25,29
再乘$(1−{1\over 5})$筛去2个，剩下8个数：
1,7,11,13,17,19,23,29
这是因为被筛去的数是平均分布的，则剩下的数中，为另一个素数的倍数也是平均分布的。
要合理分析题目难度，不要高估，检查时要检查所有情况，不要只盯着一个地方。
1 | #include "stdio.h" |
一般自己能独立做出的题目是不写题解的，但是这是我第一道独立做出的自己总结的 树状数组解决两个不等式限制问题 ，因此写篇题解纪念一下
设输入数据为$a_1····a_n$,若一个$(i,j)$对(设$i<j$)满足题目条件，则需满足三个条件
$$
\begin{cases}
i<j\\a[j]\ge i\\a[i]\ge j
\end{cases}
\implies
\begin{cases}
j\le min(a[i],i-1) \\ a[j]\ge i
\end{cases}
$$
化简后变为两个条件
从1到n循环
每轮循环更新update(i,1)，这样树状数组中每个为1的点都代表一个$j$
同时de[a[i]].push_back(i)，这样当$i$递增到$a[i]$时，下轮循环$i$递增不再满足$a[j]\ge i$，此时de[i]中有应该删除的$j$点，对这些点update(j,-1)即可保证树状数组中的点都满足第二个条件。
再通过sum(min(a[i],i-1))完成对第一个条件的限制，可求得同时满足两个条件的$j$点的个数,问题得解。
1 | #include <bits/stdc++.h> |
ZOJ 4008 Yet Another Tree Query Problem
HDU-6230 HDU-5542 利用树状数组解决两个不等式限制的问题
给出一些点，判断这些点能否都在小于等于两条直线上
首先找出三个不在一条直线上的点，可以得到三条直线。
依次枚举每条直线可解。
1 | #include <cstdio> |
首先应该想到，同学们会被划分成$gcd(n,k+1)$个集合，同一个集合内的同学之间才能互相交换硬币。对每个集合，问题被化简成如下情况。
$\require{AMScd}$
$$
\begin{CD}
a_0 @>x_0>> a_1\\
@A x_3 A A @VV x_1 V\\
a_3 @<<x_2< a_2
\end{CD}
$$
其中$x$表示按箭头方向传递硬币的数量，为负代表按与箭头相反的方向传递硬币。
环状方程问题应想到当确定一个变量时，其他所有变量都可得出
设$x_0$为常量,$avg$为每个人最后应拥有的硬币
得出方程
$$
a_1+x_0-x_1=avg \\ x_1=-avg+a_1+x_0
$$
$$
a_2+x_1-x_2=avg
$$
带入$x_1$
$$
x_2=-2avg+a_1+a_2+x_0
$$
以此类推得到公式
$$x_i=-i*avg+\sum_{j=1}^i a_j+x_0 $$
答案需要求总移动次数 $\sum_{i=0}^{n-1}|x_i|$
而
$$
|x_i|=|i*avg-\sum_{j=1}^i a_i-x_0|$$
相当于在数轴上求一点 $x_0$ 使其到各点 $i*avg-\sum_{j=1}^ia_i$ 的距离之和最小
排序之后求中位数即可
$dp[i]$表示前i个数字组成的最小答案，得到状态转移方程
$$ dp[i]={min(\\
dp[i-1]+a[i],\\
dp[i-c]+\sum_{j=i-c+1}^{i}a[i]-\min_{j=i-c+1}^{i}a[i]
\\) }
$$
维护动态集合（有不停的添加删除元素）的最小值用muiltset
解题时要想到枚举思路，dp，二分，贪心等常用思路都要考虑到。当确定$dp[i]$的意义后，要大胆的写出方程。
1 | #include "bits/stdc++.h" |
给定$n$，求${1\over x}+{1\over y}={1\over n} (x\le y) $的解数(x、y、n均为正整数)
化简方程
$$
nx+ny=xy
$$
代入
$$
\\
\begin{cases}
x=n+a\\
y=n+b
\end{cases}
\\
$$
得
$$
n^2=ab
$$
即为求$n^2$的约数个数，约数个数定理可解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#include <cstdio>
#include <cstring>
#include <algorithm>
#include "iostream"
#include <cmath>
#include <vector>
#include "set"
using namespace std;
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
typedef long long ll;
const ll INF = 1e18;
const ll MAXN =1e5+100;
const ll MOD = 1e9+7;
const ll LIM= 1e5;
int prime[LIM+100],cnt;
bool isprime[LIM+100];
void linear()
{
cnt=0;
memset(isprime,1,sizeof(isprime));
isprime[1]=false;
for(int i=2;i<=LIM;i++)
{
if(isprime[i])prime[cnt++]=i;
for(int j=0;j<cnt&&i*prime[j]<=LIM;j++)
{
isprime[i*prime[j]]=false;
if(i%prime[j]==0)break;
}
}
}
int main(int argc, char const *argv[]) {
// FOP;
linear();
ll T_T;
cin>>T_T;
while(T_T--)
{
ll n;
cin>>n;
ll po[100];
ll idx=0;
Met(po,0);
for(int i=0;i<cnt && prime[i]<=n;++i)
if(!(n%prime[i]))
{
while (n%prime[i]==0) {
n/=prime[i];
po[idx]++;
}
idx++;
}
if(n>1)
{
po[idx]=1;
idx++;
}
ll ans=1;
for(int i=0;i<idx;++i)
ans*=po[i]*2+1;
cout<<(ans/2)+1<<endl;
}
return 0;
}