2816. Troywar loves Maths
★★☆ 输入文件：Troy_1.in 输出文件：Troy_1.out 简单对比
时间限制：1 s 内存限制：256 MB
【题目描述】
众所周知，Troywar总是不好好上课看数（xiao）论（shuo）。一天数学老师是在看不下去了，于是决定考（jiao）考（xun）他一下。于是，扔给了Troywar一个问题：给定两个正整数n和m，有多少对1<=i<=n，1<=j<=m使得$a=2^{i}+1,b=2^{j}+1$满足a和b的最大公约数为3。翘课的Troywar当然不会了，他只好求助你。
【输入格式】
两个正整数n,m
【输出格式】
一个整数。
【样例输入】
10 10
【样例输出】
19
【数据范围】
1.10% n,m<=63
2.另有20%数据保证n，m<=1000
3.另有20%数据保证n<=3
4.对于所有数据，保证n,m<=1e7
【来源】
题解：
第一次出题，也不知道有没有人做……我们先把n调成n，m中小的，m为较大的。
$\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(2^{i}+1,2^{j}+1)==3]$
$首先，我们的要求是3|2^{x}+1$
$2^x+1\equiv 2^{x\,\bmod \phi(3)}+1(\bmod)3$
$所以当x为奇数时才可能成立,先令i>j$
$\;\;\;\;\gcd(2^{i}+1,2^{j}+1)=\gcd(2^{i}-2^{j},2^j+1)$
$=\gcd（2^{i-j}-1,2^j+1）$
$=\gcd (2^{i-j}+2^j,2^j+1)$
$若i-j>j$
$\gcd(2^{i}+1,2^{j}+1)=\gcd(2^{i-2j}+1,2^j+1)$
$否则$
$\gcd(2^{i}+1,2^{j}+1)=\gcd(2^{2j-i}+1,2^j+1)$
$联系辗转相除$
$\gcd(2^{i}+1,2^{j}+1)=2^{\gcd(i,j)}+1$
$所以有gcd(i,j)==1且i、j为奇数$
$\therefore Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)==1\&i、j为奇数] $
$=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==1]-\sum_{i=1}^{\lfloor \frac n 2\rfloor}\sum_{j=1}^{m}[gcd(i,j)==1]-\sum_{i=1}^{\lfloor \frac m 2\rfloor}\sum_{j=1}^{n}[gcd(i,j)==1]$
$=\sum_{d=1}^{n}\mu(d)\lfloor \frac m d\rfloor\lfloor \frac n d\rfloor-\sum_{d=1}^{n}\mu(d)\lfloor \frac m d\rfloor\lfloor \frac n {kd}\rfloor-\sum_{d=1}^{n}\mu(d)\lfloor \frac m {kd}\rfloor\lfloor \frac n d\rfloor$
$其中当d为奇数时，k为2，否则k为1$
对于前10%是为了给暴力分……至于n<=3是为了打表找规律，再结合前10%验证。n,m小于1000……当作给不会反演的分吧……
标程：
#define Troy 09/29/2017 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e7+; int miu[N],prim[N/],num,sum[N];
bool vis[N]; inline void init(){
miu[]=;
sum[]=;
for(int i=;i<N;i++){
if(!vis[i])
prim[++num]=i,miu[i]=-;
for(int j=;prim[j]*i<N;j++){
vis[i*prim[j]]=;
if(i%prim[j]==){
miu[i*prim[j]]=;
break;
}
miu[i*prim[j]]=-miu[i];
}
sum[i]=sum[i-]+miu[i];
}
} int n,m; int main(){ init();
freopen("Troy_1.in", "r", stdin);
freopen("Troy_1.out","w",stdout);
scanf("%d%d",&n,&m);
if(n>m) n^=m^=n^=m;
ll ans=;
for(int i=;i<=n;i++){
ll t=1ll*miu[i]*(n/i)*(m/i),d;
if(i&){
d=1ll*miu[i]*(1ll*(n/i)*(m/i/)+1ll*(n/i/)*(m/i));
}
else
d=1ll**miu[i]*(n/i)*(m/i);
ans+=t-d;
}
printf("%lld\n",ans);
}