HDU4611+数学

 /*

 找规律

 题意：abs(i%A - i%B) 对i从0~N-1求和

 从0~N-1一个一个算必TLE，着A，B两者差相同的部分合并起来算

 */

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 #include<algorithm>

 #include<iostream>

 #include<queue>

 #include<map>

 #include<math.h>

 using namespace std;

 typedef long long int64;

 //typedef __int64 int64;

 const int maxn = ;

 const int inf = 0x7fffffff;

 const double pi=acos(-1.0);

 const double eps = 1e-;

 int64 gcd( int64 a,int64 b ){

     int64 r;

     while( b ){

         r = a%b;

         a = b;

         b = r;

     }

     return a;

 }

 int64 lcm( int64 a,int64 b,int64 Gcd ){

     return a*b/Gcd;

 }

 int64 Abs( int64 a ){

     if( a< ) return -a;

     else return a;

 }

 int64 solve( int64 n,int64 a,int64 b ){

     int64 Index,tmpLen,res,Indexa,Indexb;

     res = Index = Indexa = Indexb = ;

     while( Index<n ){

         tmpLen = min( a-Indexa,b-Indexb );

         if( Index+tmpLen>n ) tmpLen = n-Index;//Index:表示新的开始分割的位置

         res += tmpLen*Abs( Indexa-Indexb );

         Indexa += tmpLen, Indexa %= a;

         Indexb += tmpLen, Indexb %= b;

         Index += tmpLen;

     }

     return res;

 }

 int main(){

     int T;

     scanf("%d",&T);

     while( T-- ){

         int64 n,a,b;

         //scanf("%lld%lld%lld",&n,&a,&b);

         scanf("%I64d%I64d%I64d",&n,&a,&b);

         int64 LCM = lcm( a,b,gcd(a,b) );

         int64 ans = ;

         if( LCM>=n ) ans = solve( n,a,b );

         else ans = (n/LCM)*solve( LCM,a,b )+solve( n%LCM,a,b );

         //printf("%lld\n",ans);

         printf("%I64d\n",ans);

     }

     return ;

 }