対角線がN個の正方形を通過する明確な矩形の数

Question

私はCSの問題を解決しています。私は数Nを持っており、サイズが1x1の長方形に矩形が分割されている場合、対角線がN個の正方形で渡っている別々の矩形の数を数える必要があります。この写真はあなたが理解するのに役立ちます。

N = 4の場合、この画像は、すべての4つの組み合わせを示している、対角4つの正方形に通過された実際の矩形はサイズが1×4、2×、4×2と4×4です。

我々はそれがある長方形の2つのサイズ与えた場合、私は式が見つかりました：

A + B -^6 N < = 10ので、GCD（A、B）

を、私は上がりますAの除数がgcd（A、B）なので、Nの除数NをNで除算すると、O（N sqrt（N））となります。qは除数です。 qは除数です。 （A、B）= 0 これはO（N sqrt（N）* log（N））の でこれを解決しました。 log（N）は2のgcdを見つける時間です数字。

制限時間は3秒ですので、時間通りに失敗します。ソリューションを最適化するための助けが必要です。

更新：事前に

#include <bits/stdc++.h> 

#define ll long long 
using namespace std; 
int a; 

int gcd(int a, int b) { 
    if(b>a) swap(a,b); 
    if(b==0) return a; 
    return gcd(b, a%b); 
} 

bool valid(int n, int m, int gc, int a) { 
    if(n+m-gc==a) return true; 
    return false; 
} 

int main() { 
cin>>a; 

int counter=0; 
for(int i=1;i<=a/2;i++) { 
    for(ll j=1;j<=sqrt(i);j++) { 
     if(i%j==0) { 
      if(j!=i/j) { 
       int m1 = a+j-i; 
       int div=i/j; 
       int m2 = a+div-i; 
       if(valid(i, m1, j, a)) { 
        if(gcd(i, m1)==j) 
         counter++; 
       } 
       if(valid(i, m2, i/j, a)) { 
        if(gcd(i,m2)==i/j) 
         counter++; 
       } 

      } 
      else { 
       int m1 = a+j-i; 
       if(valid(i, m1, j, a)) { 
        if(gcd(i, m1)==j) 
         counter++; 
       } 
      } 
     } 
    } 
} 
cout<<counter+1; 
return 0; 
} 

ありがとう：ここに私のコードです。

Answer 1

O(n*sqrt(n)*log(n))がn <= 10^6ために少しくらいの音、そしてあなたはおそらく若干良いアルゴリズムを必要とする、あなたのコードは、いくつかの最適化をサポートしていますが：

int gcd(int a, int b) { 
    if(b>a) swap(a,b); 
    if(b==0) return a; 
    return gcd(b, a%b); 
} 

はスワップを取り除く、それはそれなしでうまく動作します。

あなたはそれに取り組んでいる一方で、あまりにも再帰を取り除く：

int gcd(int a, int b) { 
    while (b) { 
     int r = a % b; 
     a = b; 
     b = r; 
    } 

    return a; 
} 

次へ：それぞれのループの

for(int i=1;i<=a/2;i++) { 
    for(ll j=1;j<=sqrt(i);j++) { 

計算a/2とsqrt(i)外側を。各反復でそれを計算する必要はありません。コンパイラはこれを行うには十分にスマートな（またはセットアップする）かもしれませんが、特にオンラインジャッジの設定に頼るべきではありません。

さらに毎回i/jを再計算しないように事前に計算することもできます。多くの部門が遅くなる可能性があります。

次に、jにはlong longが本当に必要ですか？ iはintであり、jはその平方根になります。したがって、jにはlong longは必要ありません。intを使用してください。