Опытный
Профиль
Группа: Участник
Сообщений: 722
Регистрация: 30.3.2006
Репутация: 27
Всего: 32
|
| Цитата(armageddon @ 7.4.2006, 17:49) | еще одна задача с тем же вопросом типа:
(991*n*n)+1 считалось до появления ЭВМ точным не квадратом, как найти такое n, при котором находится такое число |
Ну, для этого придётся решать уравнение Пелля (вида x^2 – m*y^2 = 1) в целых числах. Это будет что-то вроде: | Код | // Win32 Application
#include <windows.h>
HWND hWnd;
HWND Button;
HWND Edit1, Edit2, Edit3;
LRESULT CALLBACK WndProc(
HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam);
void Solve();
void InitWindow(HINSTANCE hInstance, int nCmdShow)
{
const char WndClass[] = "MainWindow";
const char WndTitle[] = "Solver";
WNDCLASSEX wcex = {0};
wcex.cbSize = sizeof(wcex);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = WndProc;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(NULL, IDI_APPLICATION);
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW);
wcex.lpszClassName = WndClass;
wcex.hIconSm = LoadIcon(NULL, IDI_APPLICATION);
RegisterClassEx(&wcex);
const WndWidth = 500;
const WndHeight = 210;
int WndX = (GetSystemMetrics(SM_CXSCREEN)-WndWidth)/2;
int WndY = (GetSystemMetrics(SM_CYSCREEN)-WndHeight)/2;
hWnd = CreateWindow(WndClass, WndTitle, WS_MINIMIZEBOX | WS_SYSMENU,
WndX, WndY, WndWidth, WndHeight,
NULL, NULL, hInstance, NULL);
Button = CreateWindow(
"Button", "Solve",
WS_CHILD | WS_VISIBLE,
200, 150, 85, 25,
hWnd, NULL, hInstance, NULL);
Edit1 = CreateWindow(
"Edit", "991",
WS_CHILD | WS_VISIBLE | WS_BORDER | ES_NUMBER,
30, 40, 435, 20,
hWnd, NULL, hInstance, NULL);
Edit2 = CreateWindow(
"Edit", "",
WS_CHILD | WS_VISIBLE | WS_BORDER | ES_READONLY,
30, 80, 435, 20,
hWnd, NULL, hInstance, NULL);
Edit3 = CreateWindow(
"Edit", "",
WS_CHILD | WS_VISIBLE | WS_BORDER | ES_READONLY,
30, 110, 435, 20,
hWnd, NULL, hInstance, NULL);
HWND Static1 = CreateWindow(
"Static", "m = ",
WS_CHILD | WS_VISIBLE,
10, 40, 18, 20,
hWnd, NULL, hInstance, NULL);
HWND Static2 = CreateWindow(
"Static", "x = ",
WS_CHILD | WS_VISIBLE,
10, 80, 18, 20,
hWnd, NULL, hInstance, NULL);
HWND Static3 = CreateWindow(
"Static", "y = ",
WS_CHILD | WS_VISIBLE,
10, 110, 18, 20,
hWnd, NULL, hInstance, NULL);
HWND Static4 = CreateWindow(
"Static", "x^2 - m*y^2 = 1",
WS_CHILD | WS_VISIBLE,
205, 10, 80, 20,
hWnd, NULL, hInstance, NULL);
HFONT hFont = CreateFont(
12, 0, 0, 0, 400, 0, 0, 0, DEFAULT_CHARSET,
OUT_DEFAULT_PRECIS, CLIP_DEFAULT_PRECIS,
DEFAULT_QUALITY, DEFAULT_PITCH | FF_DONTCARE,
"MS Sans Serif");
SendMessage(Button, WM_SETFONT, (WPARAM)hFont, 0);
SendMessage(Edit1, WM_SETFONT, (WPARAM)hFont, 0);
SendMessage(Edit2, WM_SETFONT, (WPARAM)hFont, 0);
SendMessage(Edit3, WM_SETFONT, (WPARAM)hFont, 0);
SendMessage(Static1, WM_SETFONT, (WPARAM)hFont, 0);
SendMessage(Static2, WM_SETFONT, (WPARAM)hFont, 0);
SendMessage(Static3, WM_SETFONT, (WPARAM)hFont, 0);
SendMessage(Static4, WM_SETFONT, (WPARAM)hFont, 0);
ShowWindow(hWnd, nCmdShow);
}
int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE, LPTSTR, int nCmdShow)
{
InitWindow(hInstance, nCmdShow);
MSG msg;
while (GetMessage(&msg, 0, 0, 0))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
return int(msg.wParam);
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam)
{
switch (uMsg)
{
case WM_COMMAND:
if (HIWORD(wParam)==BN_CLICKED && lParam==LPARAM(Button))
Solve();
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, uMsg, wParam, lParam);
}
return 0;
}
template <int nBits>
struct s_Int
{
char Bit[nBits];
int N;
bool Sign; // Value<0 <=> Sign == true
s_Int()
{
N = 0;
Sign = false;
}
s_Int(const s_Int &Val)
{
N = Val.N;
Sign = Val.Sign;
for (int i=0; i<=N; i++)
Bit[i] = Val.Bit[i];
}
s_Int(int Val)
{
N = 0;
Sign = Val<0;
Val = Sign ? -Val : Val;
for (int i=0; i<8*sizeof(int)-1; i++)
if (Bit[i] = (Val>>i) & 1)
N = i;
}
s_Int operator =(s_Int Val)
{
N = Val.N;
Sign = Val.Sign;
for (int i=0; i<=N; i++)
Bit[i] = Val.Bit[i];
return *this;
}
friend s_Int operator -(s_Int Val)
{
Val.Sign ^= true;
return Val;
}
friend s_Int operator +(s_Int Val1, s_Int Val2)
{
s_Int Res;
int i;
if (!Val1.Sign && !Val2.Sign)
{
if (Val1.N < Val2.N)
return Val2+Val1;
char Inc = 0;
for (i=0; i<=Val2.N; i++)
{
Res.Bit[i] = Val1.Bit[i] + Val2.Bit[i] + Inc;
Inc = Res.Bit[i]>1;
Res.Bit[i] &= 1;
}
for (i=Val2.N+1; i<=Val1.N; i++)
{
Res.Bit[i] = Val1.Bit[i] + Inc;
Inc = Res.Bit[i]>1;
Res.Bit[i] &= 1;
}
Res.Bit[i] = Inc;
Res.N = Inc ? i : i-1;
Res.Sign = false;
return Res;
}
if (!Val1.Sign && Val2.Sign)
{
if (Val1<-Val2)
return -(-Val2-Val1);
char Dec = 0;
for (i=0; i<=Val2.N; i++)
{
Res.Bit[i] = Val1.Bit[i] - Val2.Bit[i] - Dec + 2;
Dec = Res.Bit[i]<2;
if (Res.Bit[i] &= 1)
Res.N = i;
}
for (i=Val2.N+1; i<=Val1.N; i++)
{
Res.Bit[i] = Val1.Bit[i] - Dec + 2;
Dec = Res.Bit[i]<2;
if (Res.Bit[i] &= 1)
Res.N = i;
Res.Sign = false;
}
}
if (Val1.Sign && !Val2.Sign)
return Val2 + Val1;
if (Val1.Sign && Val2.Sign)
return -(-Val1 + -Val2);
return Res;
}
friend s_Int operator -(s_Int Val1, s_Int Val2)
{
return Val1 + -Val2;
}
friend s_Int operator *(s_Int Val1, s_Int Val2)
{
if (Val1.N < Val2.N)
return Val2*Val1;
s_Int Res;
memset(Res.Bit, 0, Val1.N+Val2.N+2);
int i;
for (i=0; i<=Val2.N; i++)
if (Val2.Bit[i])
{
char Inc = 0;
for (int j=0; j<=Val1.N; j++)
{
Res.Bit[i+j] += Val1.Bit[j]+Inc;
Inc = Res.Bit[i+j]>1;
Res.Bit[i+j] &= 1;
}
Res.Bit[i+j]+=Inc;
}
for (i=Val1.N+Val2.N+1; i && !Res.Bit[i]; i--);
Res.N=i;
Res.Sign = Val1.Sign ^ Val2.Sign;
return Res;
}
friend s_Int operator /(s_Int Val1, s_Int Val2)
{
Val1.Modulo(Val2, true);
return Val1;
}
friend s_Int operator %(s_Int Val1, s_Int Val2)
{
return Val1.Modulo(Val2, false);
}
friend bool operator <(s_Int Val1, s_Int Val2)
{
if (Val1.Sign && !Val2.Sign)
return true;
if (!Val1.Sign && Val2.Sign)
return false;
if (Val1.Sign && Val2.Sign)
return -Val2<-Val1;
if (Val1.N < Val2.N)
return true;
if (Val1.N > Val2.N)
return false;
for (; Val1.N; Val1.N--)
if (Val1.Bit[Val1.N] < Val2.Bit[Val1.N])
return true;
else if (Val1.Bit[Val1.N] > Val2.Bit[Val1.N])
return false;
return *Val1.Bit < *Val2.Bit;
}
friend bool operator <=(s_Int Val1, s_Int Val2)
{
if (Val1.Sign && !Val2.Sign)
return true;
if (!Val1.Sign && Val2.Sign)
return false;
if (Val1.Sign && Val2.Sign)
return -Val2<-Val1;
if (Val1.N < Val2.N)
return true;
if (Val1.N > Val2.N)
return false;
for (; Val1.N; Val1.N--)
if (Val1.Bit[Val1.N] < Val2.Bit[Val1.N])
return true;
else if (Val1.Bit[Val1.N] > Val2.Bit[Val1.N])
return false;
return *Val1.Bit <= *Val2.Bit;
}
friend bool operator ==(s_Int Val1, s_Int Val2)
{
if (Val1.Sign ^ Val2.Sign)
return false;
if (Val1.N < Val2.N || Val1.N > Val2.N)
return false;
for (; Val1.N; Val1.N--)
if (Val1.Bit[Val1.N] != Val2.Bit[Val1.N])
return false;
return *Val1.Bit == *Val2.Bit;
}
s_Int Modulo(s_Int Divider, bool bDivThis)
{
s_Int Val = *this;
if (Divider.N > Val.N)
{
*this = 0;
return Val;
}
int N = Divider.N+1;
Val.Bit[Val.N+1] = 0;
Divider.Bit[N] = 0;
char *p1 = Val.Bit+Val.N+1;
char *p2 = Divider.Bit+N;
s_Int PreRes, Res;
int i, n=-1;
for (; p1-N+1 != Val.Bit; p1--)
{
bool b = true;
for (i=0; i<=N; i++)
if (p1[-i]>p2[-i])
break;
else if (p1[-i]<p2[-i])
{
b = false;
break;
}
if (b)
{
int Dec = 0;
for (i=N; i>=0; i--)
{
p1[-i] -= p2[-i]+Dec-2;
Dec = p1[-i]<2;
p1[-i] &= 1;
}
PreRes.Bit[++n] = 1;
}
else
PreRes.Bit[++n] = 0;
}
for (i=0; i<=n; i++)
{
Res.Bit[i] = PreRes.Bit[n-i];
if (Res.Bit[i])
Res.N = i;
}
Val.N = 0;
for (i=0; i<=Divider.N; i++)
if (Val.Bit[i])
Val.N = i;
if (bDivThis)
*this = Res;
return Val;
}
s_Int Sqr()
{
return *this * *this;
}
s_Int IntSqrt()
{
s_Int Res;
Res.N = N/2;
memset(Res.Bit, 0, N);
Res.Bit[N] = 1;
while (!(Res.Sqr()<=*this && *this<(Res+1).Sqr()))
Res = (Res + *this/Res)/2;
return Res;
}
void SPrint(char *S, int nMaxCount)
{
if (nMaxCount<=0)
return;
char PreS[nBits];
s_Int Val = *this;
s_Int Mod;
int n = -1;
do
{
Mod = Val.Modulo(10, true);
PreS[++n] = '0';
for (int i=0; i<=Mod.N; i++)
PreS[n] += Mod.Bit[i]*(1<<i);
}
while (Val.N || *Val.Bit);
S[0] = '-';
if (n+Sign>=nMaxCount-2)
n = nMaxCount-2-Sign;
for (int i=0; i<=n; i++)
S[n-i+Sign] = PreS[i];
S[i+Sign] = 0;
}
};
template <int nBits>
struct s_SqrtNum // Number: (sqrt(m)+A)/B
{
s_Int<nBits> A,B,m;
s_SqrtNum()
{
}
s_SqrtNum(int m)
{
this->m = m;
A = 0;
B = 1;
}
s_SqrtNum (const s_SqrtNum &Num)
{
A = Num.A;
B = Num.B;
m = Num.m;
}
s_SqrtNum operator =(s_SqrtNum Num)
{
A = Num.A;
B = Num.B;
m = Num.m;
return *this;
}
s_Int<nBits> Get_q()
{
s_Int<nBits> NumFloor = (m.IntSqrt()+A)/B;
SetNew(NumFloor);
return NumFloor;
}
void SetNew(s_Int<nBits> NumFloor)
{
A = NumFloor*B - A;
B = (m - A.Sqr())/B;
}
};
s_Int<0x1000> P[3], Q[3], q;
void Solve()
{
char S[0x1000];
int m;
GetWindowText(Edit1, S, 0x1000);
m = (int)atof(S);
s_SqrtNum<0x1000> a(m);
P[0] = 1;
Q[0] = 0;
P[1] = a.Get_q();
Q[1] = 1;
for (;;)
{
q = a.Get_q();
P[2] = q*P[1] + P[0];
Q[2] = q*Q[1] + Q[0];
P[0] = P[1];
Q[0] = Q[1];
P[1] = P[2];
Q[1] = Q[2];
if (P[2].Sqr()-Q[2].Sqr()*m==1)
break;
}
P[2].SPrint(S, 0x1000);
SetWindowText(Edit2, S);
Q[2].SPrint(S, 0x1000);
SetWindowText(Edit3, S);
} |
В данном случае твоё наименьшее n = 12055735790331359447442538767
|
точный вывод числа 
Загрузка ...
Solver.cpp 11,00 Kb
