传送门
文章目录
- 题意：
- 思路：
题意：
给三个数 c , d , x c,d,x c,d,x，求满足 c ∗ l c m ( a , b ) − d ∗ g c d ( a , b ) = x c*lcm(a,b)-d*gcd(a,b)=x c∗lcm(a,b)−d∗gcd(a,b)=x条件的 ( a , b ) (a,b) (a,b)的数量。
思路：
考虑将
l
c
m
(
a
,
b
)
lcm(a,b)
lcm(a,b)表示成
k
∗
g
c
d
(
a
,
b
)
k*gcd(a,b)
k∗gcd(a,b)，随后将式子化简
(
c
∗
k
−
d
)
∗
g
c
d
(
a
,
b
)
=
x
(c*k-d)*gcd(a,b)=x
(c∗k−d)∗gcd(a,b)=x，现在我们只需要求
x
x
x的因子，之后让一个因子
x
z
frac{x}{z}
zx等于
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b)，
z
z
z等于
(
c
∗
k
−
d
)
(c*k-d)
(c∗k−d)即可。因为
c
,
d
c,d
c,d都知道了，那么容易得出
k
=
d
+
z
c
k=frac{d+z}{c}
k=cd+z，当然前提是
(
d
+
z
)
m
o
d
c
=
0
(d+z)bmod c=0
(d+z)modc=0。
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b)已知，
l
c
m
(
a
,
b
)
=
k
∗
g
c
d
(
a
,
b
)
lcm(a,b)=k*gcd(a,b)
lcm(a,b)=k∗gcd(a,b)，只需要求出满足
l
c
m
(
a
,
b
)
lcm(a,b)
lcm(a,b)和
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b)的
(
a
,
b
)
(a,b)
(a,b)对数即可。
我们将
a
,
b
a,b
a,b都除
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b)，那么
g
c
d
(
a
′
,
b
′
)
=
1
gcd(a^{'},b^{'})=1
gcd(a′,b′)=1,
l
c
m
(
a
′
,
b
′
)
=
l
c
m
(
a
,
b
)
g
c
d
(
a
,
b
)
=
a
′
∗
b
′
lcm(a^{'},b^{'})=frac{lcm(a,b)}{gcd(a,b)}=a^{'}*b^{'}
lcm(a′,b′)=gcd(a,b)lcm(a,b)=a′∗b′，我们对
a
′
∗
b
′
a^{'}*b^{'}
a′∗b′进行质因子分解，得到
a
′
∗
b
′
=
p
1
k
1
p
2
k
2
.
.
.
p
n
k
n
a^{'}*b^{'}=p_1^{k_1}p_2^{k_2}...p_n^{k_n}
a′∗b′=p1k1p2k2...pnkn，也就相当于从质因子中找出来一些分给
a
′
a^{'}
a′和
b
′
b^{'}
b′，又因为
g
c
d
(
a
′
,
b
′
)
=
1
gcd(a^{'},b^{'})=1
gcd(a′,b′)=1，所以他们不能有相等的质因子，所以一个质因子只能给一个数。假设有
c
n
t
cnt
cnt个质因子，那么组合就有
2
c
n
t
2^{cnt}
2cnt种组合。这样问题就解决啦。
之前代码t掉啦，改成线性筛就好了。
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std; //void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); } typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; const int N=20000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6; LL ans=0; int c,d,x; int st[N],nt[N]; int mp[N]; int prime[N],cnt; vector<int>v; void solve(int y) { if((y+d)%c!=0) return; LL k=(y+d)/c; int cnt=0; while(k!=1) { int x=nt[k]; cnt++; while(k%x==0) k/=x; } ans+=(1<<cnt); } int main() { // ios::sync_with_stdio(false); // cin.tie(0); for(int i=2;i<N;i++) { if(!st[i]) prime[cnt++]=i,nt[i]=i; for(int j=0;prime[j]<=N/i;j++) { st[prime[j]*i]=true; nt[prime[j]*i]=prime[j]; if(i%prime[j]==0) break; } } int _; scanf("%d",&_); while(_--) { ans=0; scanf("%d%d%d",&c,&d,&x); vector<int>vv; for(int i=1;i<=x/i;i++) if(x%i==0) { int a=i,b=x/i; if(a!=b) vv.pb(a),vv.pb(b); else vv.pb(a); } for(int i=0;i<vv.size();i++) solve(vv[i]); printf("%lldn",ans); } return 0; } /* */
最后
以上就是敏感方盒最近收集整理的关于Educational Codeforces Round 106 (Rated for Div. 2) D. The Number of Pairs 数论gcd题意：思路：的全部内容，更多相关Educational内容请搜索靠谱客的其他文章。
发表评论 取消回复