SRM346 DIV2

500pt

You will be given a vectora and two ints lower and upper.
Return the number of integers between lower and upper, inclusive, that are multiples of all members of a.
問題文の意味を理解するまで時間かかったｗ
multipleは掛け算を意味するものだと思ってました。正しくは倍数。

普通にlowerからupperまで順に調べると最悪2000000000*50になりTLE。
配列aの最小公倍数が分かれば、lowerからupperまでの個数が一発で分かる。
最小公倍数は a*b/gcd(a,b) で求められる。gcdは最大公約数。

class CommonMultiples
{
private: 
  int gcd(int x,int y)
    {
      return x%y?gcd(y,x%y):y;
    }
public:
  int countCommMult(vector<int> a, int lower, int upper)
    {
      int i;
      long long t=1;
      for(i=0;i<a.size();i++){
        int tmp=gcd(a[i],t);
        t*=a[i]/tmp;
        if(t>2000000000)return 0;
      }

      int re=upper/t;
      re-=(lower-1)/t;
      return re;
    }
};

ちょっとしたこと

オーバーフローについて。

main()
{
  printf("%d\n",(1<<30)*10/16);
  printf("%d\n",(1<<30)/16*10);
}

実行結果は、
-134217728
671088640
当たり前の結果だけど、見落としやすいかも。