hdu GuGuFishtion 6390 数论 欧拉函数

时间:2021-02-07 07:59:49

题目:http://acm.hdu.edu.cn/showproblem.php?pid=6390

直接开始证明:

我们设hdu GuGuFishtion 6390 数论 欧拉函数…………………………………….....…...............……………...(1)

hdu GuGuFishtion 6390 数论 欧拉函数…................................….…(2)

为什么是这样呢,因为我们知道

hdu GuGuFishtion 6390 数论 欧拉函数

hdu GuGuFishtion 6390 数论 欧拉函数

同理得到b的分解和的分解

我们会发现,虽然a和b的分解里可以有相等的部分,但是在里的也就是我们假设为的部分是不会有重复的,那么要由*得出也就是要去除重复部分,的重复部分就是a的和b的的重复部分;那么因为都是乘法,相同的部分就是最大公约数(因为每个都是素数也就是如果a和b的分解没有相同的数那么gcd(, )是不会大于1的);

由此我们开始继续对(2)的后续推论。

hdu GuGuFishtion 6390 数论 欧拉函数

我先设hdu GuGuFishtion 6390 数论 欧拉函数,那么hdu GuGuFishtion 6390 数论 欧拉函数

也就是hdu GuGuFishtion 6390 数论 欧拉函数

hdu GuGuFishtion 6390 数论 欧拉函数(看了很多博客,就给了个易得,虽然说确实很简单但是对于我这个菜鸡就不友好了)


 这一部分的证明是看了这个大佬的博客的:http://www.cnblogs.com/H-Riven/p/9494391.html

(再提供给同样是数论萌新的人一篇文库【有需要的话】:https://wenku.baidu.com/view/542961fdba0d4a7302763ad5.html

hdu GuGuFishtion 6390 数论 欧拉函数

hdu GuGuFishtion 6390 数论 欧拉函数(即在hdu GuGuFishtion 6390 数论 欧拉函数的情况下hdu GuGuFishtion 6390 数论 欧拉函数的数量)

那么我们实际上就是要求:hdu GuGuFishtion 6390 数论 欧拉函数,对于hdu GuGuFishtion 6390 数论 欧拉函数我们可以预处理得到。但是hdu GuGuFishtion 6390 数论 欧拉函数就没那么容易得到了;

现在题目就变成求对于hdu GuGuFishtion 6390 数论 欧拉函数,在hdu GuGuFishtion 6390 数论 欧拉函数hdu GuGuFishtion 6390 数论 欧拉函数的情况下有多少种方案;

这里我设hdu GuGuFishtion 6390 数论 欧拉函数hdu GuGuFishtion 6390 数论 欧拉函数的数量 (C*x表示x的倍数);即可以和HDU1695一样得到hdu GuGuFishtion 6390 数论 欧拉函数的结论

hdu GuGuFishtion 6390 数论 欧拉函数hdu GuGuFishtion 6390 数论 欧拉函数的数量

那么:

hdu GuGuFishtion 6390 数论 欧拉函数

倒过来求的原因是因为hdu GuGuFishtion 6390 数论 欧拉函数,也就是我们可以知道最后一位的准确值,那么反过来就可以推到每个位置准确值了;

那么答案就已经出来了;又因为要求的hdu GuGuFishtion 6390 数论 欧拉函数,对于每个hdu GuGuFishtion 6390 数论 欧拉函数,是含有有除法的,所以这里要用除法逆元,因为每次的mod都是不同的,所以说每次都要得到逆元,因为hdu GuGuFishtion 6390 数论 欧拉函数一定会小于min(n,m);所以说每次打从1到 min(n,m)的表比单个值的计算快;

以下是代码:

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+;
ll euler[N], inv[N]={, }, F[N], P[N], n, m, mod, mins;
void Euler(){///打欧拉表
register int i, j;
for(i=; i<N; ++i){ euler[i]=i; }
for(i=; i<N; ++i){
if(euler[i]==i){
for(j=i; j<N; j+=i)
euler[j]=euler[j]-euler[j]/i;
}
}
}
void Inv(){///打表求逆元
for(register int i=; i<=mins; ++i){
inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
}
}
int main( ){
Euler();
int T;
register ll ans;
register int i, j;
scanf("%d", &T);
while(T--){
scanf("%I64d%I64d%I64d", &n, &m, &mod);
mins=min(n, m);
Inv();
for(i=; i<=mins; ++i){
F[i]=(n/i)*(m/i)%mod;
}
for(i=mins; i>=; --i){
P[i]=F[i];
for(j=; j*i<=mins; ++j){
P[i]-=P[i*j];
if(P[i]<){
P[i]+=mod;
}
}
}
ans=;
for(i=; i<=mins; ++i){
ans=(ans+(i*inv[euler[i]]%mod)*P[i]%mod)%mod;
}
printf("%I64d\n", ans);
}
}

拙劣的代码