题目
做法
假设有(P)个完整的循环块,假设此时答案为(K)(实际答案可能有多种),即每块完整块长度为(K),则(P=left lfloor frac{N}{K} ight floor)
假设循环快中有(p_a,p_b)个(A)和(B),则
-
(p_acdot Ple aLongrightarrow p_ale left lfloor frac{a}{P} ight floor)
-
(p_acdot (P+1)ge aLongrightarrow p_age lceil frac{a}{P+1} ceil)
故
[egin{aligned}\
lceil frac{a}{P+1}
ceil le p_a le left lfloor frac{a}{P}
ight
floor\
lceil frac{b}{P+1}
ceil le p_b le left lfloor frac{b}{P}
ight
floor\
end{aligned}]
(P)可能的值可以整除分块算出来,(O(sqrt n))
Code
#include<bits/stdc++.h>
typedef int LL;
LL a,b,ans;
int main(){
scanf("%d%d",&a,&b);
LL len(a+b);
for(LL i=1,r;i<=len;i=r+1){
LL P(len/i);
r=len/P;
if(P>a || P>b) continue;
LL an((a+P)/(P+1)),ax(a/P),bn((b+P)/(P+1)),bx(b/P);
if(an<=ax && bn<=bx) ans+=std::min((ax+bx),r)-std::max((an+bn),i)+1;
}
printf("%d ",ans);
return 0;
}