2 つの整数 L と R が与えられた場合、L と R の間で約数の約数を持つ整数の数を見つけることが期待されます。
入力フォーマット:
最初の行には、テスト ケースの数である単一の整数 T が含まれています。次の T 行のそれぞれには、i 番目のテスト ケースのパラメーターを示す、スペースで区切られた 2 つの整数 Li と Ri が含まれます。
制約
1≦T≦10000
1≦L≦R≦10^18
#include <stdio.h>
int main(void)
{
int t;
long int cnt,countj;
scanf("%d",&t);
long long int l[t], r[t];
int i=0;
for(i=0;i<t;i++){
scanf("%d%d",&l[i],&r[i]);
}
int div[t];
for(i=0;i<t;i++){
//count[i]=0;
cnt=0;
for(int j=l[i]+1;j<r[i];j++){
countj=0;
for(int k=1;k<=j/2;k++){
if(j%k==0)
countj++;
}
if ((countj%2)==0)
cnt++;
}
printf("%ld\n",cnt);
}
return 0;
}
このプログラムは実行に時間がかかりすぎます。特に数値が大きい場合、どのように最適化できますか? そして、それはすべてのテスト ケースに合格しませんでしたが、コードのどのようなエラーが考えられますか?
問題が実際に説明したとおりである場合、パフォーマンスを改善する方法は数多くありますが、そのうちの 1 つだけを以下に示しますが、最初に達成しようとしているものの背後にある理論を理解する必要があります。
除数が奇数の整数は、常に完全な二乗です。いくつかの番号が与えられNた場合、X除数があり、いくつかの対応がなければならないYことなどXY=Nも当てはまります。彼らは常にペアで来ます。例外は完全な正方形です。その場合、それらの数にはWなどの約数がありWW=N、1 つの約数Wとしてのみカウントされます。したがって、奇数の約数があります。N
それで、これはどのように役立ちますか？さて、あなたの述べたタスクは、からすべての整数を見つけることですLを通じてR約数の奇数数を持ちます。しかし、私たちは完全な正方形だけがそのような性質を持っていることを示しました. したがって、その質問が本当に求めていることは次のとおりです。
2 つの整数
Lと の間の完全平方の数を見つけますR。
そのようなアルゴリズムの 1 つは、単純に次のようなものです。
Lテスト番号の浮動小数点平方根を取ることから始めますR、またはいずれか早い方完璧な広場、見つける最初に。完全な正方形が見つからなかった場合、答えは 0 で終了です。完璧な正方形を見つけた場合、 と の間Lで徐々にループする必要はなくなりますR。開始点 (完全な根) があり、その平方が を超える までその根を徐々に増やしてループしますR。これにより、反復回数が大幅に削減されます。
以下のコードでは：
T : テストの数L : テストシリーズの最初の数R : テスト シリーズの最後の番号N：奇数除数の値の数との間L及びR 包括的なsr : 検出ループの実行平方根。コード
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
unsigned int T = 0;
if (scanf("%u", &T) != 1)
return EXIT_FAILURE;
while (T--)
{
unsigned int L, R, N=0, sr, i;
if (scanf("%u %u", &L, &R) != 2)
return EXIT_FAILURE;
for (i=L; i<=R; ++i)
{
sr = sqrt(i);
if (sr * sr == i)
break;
}
if (i <= R)
for (;sr*sr <= R; ++sr,++N);
printf("%u\n", N);
}
return 0;
}
入力
5
1 2
10 100
100 1000
500 2500
1 262144
出力
1
7
22
28
512
パフォーマンス
コードが少ないことを考えると、このコードはうまく機能します]。clang 3.9.1 を使用した結果の分解-x c -O2は、立派です。
.LC0:
.string "%u"
.LC1:
.string "%u %u"
.LC3:
.string "%u\n"
main:
push rbp
push rbx
xor eax, eax
mov edi, OFFSET FLAT:.LC0
mov ebp, 1
sub rsp, 40
lea rsi, [rsp+20]
mov DWORD PTR [rsp+20], 0
call __isoc99_scanf
cmp eax, 1
je .L24
.L1:
add rsp, 40
mov eax, ebp
pop rbx
pop rbp
ret
.L24:
mov ebp, eax
mov eax, DWORD PTR [rsp+20]
lea edx, [rax-1]
test eax, eax
mov DWORD PTR [rsp+20], edx
je .L25
.L3:
lea rdx, [rsp+28]
lea rsi, [rsp+24]
xor eax, eax
mov edi, OFFSET FLAT:.LC1
call __isoc99_scanf
cmp eax, 2
jne .L1
mov ebx, DWORD PTR [rsp+24]
cmp ebx, DWORD PTR [rsp+28]
jbe .L10
jmp .L11
.L26:
add ebx, 1
cmp DWORD PTR [rsp+28], ebx
jb .L11
.L10:
pxor xmm0, xmm0
mov eax, ebx
pxor xmm2, xmm2
cvtsi2sdq xmm0, rax
ucomisd xmm2, xmm0
sqrtsd xmm1, xmm0
jbe .L8
movsd QWORD PTR [rsp+8], xmm1
call sqrt
movsd xmm1, QWORD PTR [rsp+8]
.L8:
cvttsd2si rax, xmm1
mov edx, eax
mov ecx, eax
imul edx, eax
cmp edx, ebx
jne .L26
mov edi, DWORD PTR [rsp+28]
cmp ebx, edi
ja .L11
.L12:
add eax, 1
mov edx, eax
mov esi, eax
imul edx, eax
sub esi, ecx
cmp edi, edx
jnb .L12
mov edi, OFFSET FLAT:.LC3
xor eax, eax
call printf
.L27:
mov eax, DWORD PTR [rsp+20]
lea edx, [rax-1]
test eax, eax
mov DWORD PTR [rsp+20], edx
jne .L3
.L25:
xor ebp, ebp
jmp .L1
.L11:
xor esi, esi
mov edi, OFFSET FLAT:.LC3
xor eax, eax
call printf
jmp .L27
それでおしまい。それはさらに高速にすることができますが、パフォーマンスのニーズを満たす限り、おそらくそれ以上の努力の価値はありません (したがって、そうであることを願っています) 通常、奇数除数に関する質問は、最小 (または最大) の 1 つの数も要求します。除数の数、それははるかに複雑です。あなたが述べた質問はそれを求めていないため、問題は非常によく軽減されます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加