Go to Luogu to read my blog
Ideas
Another CF scam question.
for
x
x
The number selected by x is enlarged as much as possible. For
y
y
We try to make the number selected by y as small as possible, but it may be
x
x
x and
y
y
Just put the number selected by y casually.
However, you can find that according to the data range given in the question, if you find the selected number in this way, and then put the largest or smallest number, it will definitely time out.
So we can directly calculate how many there are
x
x
x How many sums are there in the selected numbers?
y
y
y The number selected and how many are selected at the same time
x
x
x and
y
y
The number selected by y is enough.
Obviously,
x
x
x can be chosen
?
n
x
?
\lfloor \frac n x \rfloor
?xn number,
y
y
y can choose
?
n
y
?
\lfloor \frac n y \rfloor
?yn number, simultaneously
x
x
x and
y
y
The number selected by y is
?
n
gcd
?
(
x
,
y
)
?
\lfloor \frac n {\gcd(x,y)}\rfloor
?gcd(x,y)n pieces.
So we put only
x
x
x selected
?
n
x
?
?
?
n
gcd
?
(
x
,
y
)
?
\lfloor \frac n x \rfloor-\lfloor \frac n {\gcd(x,y)}\rfloor
?xngcd(x,y)n Put all the numbers into the largest one, and use the arithmetic sequence to sum it up.
[
n
+
n
?
(
?
n
x
?
?
?
n
gcd
?
(
x
,
y
)
?
)
+
1
]
?
(
?
n
x
?
?
?
n
gcd
?
(
x
,
y
)
?
)
2
\frac {[n + n-(\lfloor \frac n x \rfloor-\lfloor \frac n {\gcd(x,y)}\rfloor) + 1]*(\lfloor \frac n x \rfloor-\lfloor \ frac n {\gcd(x,y)}\rfloor)} 2
2[n + n?(?xngcd(x,y)n) + 1]?(?xngcd(x,y)n)?.
Then put only the quilt
y
y
y selected
?
n
y
?
?
?
n
gcd
?
(
x
,
y
)
?
\lfloor \frac n y \rfloor-\lfloor \frac n {\gcd(x,y)}\rfloor
?yngcd(x,y)n Put all the numbers into the smallest, and use the arithmetic sequence to sum
(
1
+
?
n
y
?
?
?
n
gcd
?
(
x
,
y
)
?
)
?
(
?
n
y
?
?
?
n
gcd
?
(
x
,
y
)
?
)
2
\frac {(1 + \lfloor \frac n y \rfloor-\lfloor \frac n {\gcd(x,y)}\rfloor)*(\lfloor \frac n y \rfloor-\lfloor \frac n {\gcd( x,y)}\rfloor)} 2
2(1 + ?yngcd(x,y)n)?(?yngcd(x,y)n)?.
The formula looks complicated, but it is actually very simple. You can understand it by thinking about it yourself.
AC code
#include<bits/stdc + + .h>
using namespace std;
long long T,n,a,b,lc,dn,xn;
int main()
{<!-- -->
scanf("%lld", & amp;T);
while(T--)
{<!-- -->
scanf("%lld%lld%lld", & amp;n, & amp;a, & amp;b),lc=a*b/__gcd(a,b),dn=n/a-n/lc,xn= n/b-n/lc;
printf("%lld\
",(n + n-dn + 1)*dn/2-(1 + xn)*xn/2);
}
}