HDU2013第二次多校赛

/*找第一个循环节点，求出0到第一个循环节点的值，然后乘以循环个数，然后再暴力处理剩下的
一个个循环段的值的求法：设置两个参数ta,tb,记录A,B中被访问的数的位置，在设置一个i记录前一个位置
判断ta+a与tb+b哪一个大，小的那个跳转，每次都是跳到自己的循环节
在小的那个跳转到的那个数就是在大的那个中的位置，不如A=3，B=5，第一次跳转到6，且tb=0,
mod的差值就是ta+a-i*/

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
__int64 gcd(__int64 a,__int64 b)
{
    if(b==0) return a;
return gcd(b,a%b);
}
__int64 LMC(__int64 a,__int64 b)
{
return a/gcd(a,b)*b;
}
__int64 find(__int64 a,__int64 b,__int64 n)
{
__int64 indexa=0,indexb=0;
__int64 ans=0;
__int64 i=0,p=0;
while(i<n)
{
if(a+indexa>=n && b+indexb>=n)
{
ans+=p*(n-i);//n-i是个数，p是A,B中每两个数的差值，相当于p=(i%A-i%B);
i=n;
continue;
}
if(a+indexa<b+indexb)//每次都找最小的那个跳转
{
ans+=p*(indexa+a-i);
i=indexa+a;
indexa=indexa+a;
p=i-indexb;
}
else if(a+indexa==b+indexb)
{
ans+=p*(indexa+a-i);
i=indexa+a;
indexa=indexa+a;
indexb=indexb+b;
p=0;
}
else
{
ans+=p*(indexb+b-i);
i=indexb+b;
indexb=indexb+b;
p=i-indexa;
}
}
return ans;
}
int main()
{
__int64 n;
__int64 a,b,t;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d%I64d%I64d",&n,&a,&b);
if(a<b) swap(a,b);
if(a==b) { printf("0\n"); continue;}
__int64 lmc=LMC(a,b);
if(lmc>=n)
{
printf("%I64d\n",find(a,b,n) );
continue;
}
__int64 sum=find(a,b,lmc);
printf("%I64d\n",sum*(n/lmc)+find(a,b,n%lmc));
}
return 0;
}