Hướng dẫn giải của Số chính phương
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung uses math; const FINP=''; FOUT=''; MAXN=101; so:array['0'..'9'] of longint=(0,1,2,3,4,5,6,7,8,9); type big=array[0..MAXN] of longint; var f1,f2:text; n,test,t:longint; s:string; one,now,x,x2:big; cp:array[1..MAXN,1..MAXN] of boolean; f:array[0..MAXN] of int64; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure init; begin one[0]:=1; one[1]:=1; fillchar(cp,sizeof(cp),false); end; operator + (a,b:big) c:big; var i,nho:longint; begin fillchar(c,sizeof(c),0); c[0]:=max(a[0],b[0]); nho:=0; for i:=1 to c[0] do begin c[i]:=a[i]+b[i]+nho; if c[i]<10 then nho:=0 else begin nho:=1; c[i]:=c[i]-10; end; end; if nho=1 then begin inc(c[0]); c[c[0]]:=1; end; end; operator - (a,b:big) c:big; var i,nho:longint; begin fillchar(c,sizeof(c),0); c[0]:=a[0]; nho:=0; for i:=1 to c[0] do begin c[i]:=a[i]-b[i]-nho; if c[i]>=0 then nho:=0 else begin nho:=1; c[i]:=c[i]+10; end; end; while (c[0]>0) and (c[c[0]]=0) do dec(c[0]); end; operator < (a,b:big) c:boolean; var i:longint; begin if a[0]<b[0] then exit(true) else if a[0]>b[0] then exit(false); for i:=a[0] downto 1 do if a[i]<b[i] then exit(true) else if a[i]>b[i] then exit(false); exit(false); end; operator = (a,b:big) c:boolean; var i:longint; begin if a[0]<>b[0] then exit(false); for i:=1 to a[0] do if a[i]<>b[i] then exit(false); exit(true); end; operator << (a:big; x:longint) c:big; var i:longint; begin inc(a[0],x); for i:=a[0] downto x+1 do a[i]:=a[i-x]; for i:=x downto 1 do a[i]:=0; c:=a; end; procedure inp; inline; begin readln(f1,s); n:=length(s); end; procedure ans; inline; begin writeln(f2,f[n]); end; procedure kt(i,j:longint); inline; begin while (j<=n) do begin now:=now<<2; now[2]:=so[s[j-1]]; now[1]:=so[s[j]]; x:=x<<1; x2:=x2<<2; while x2<now do begin x2:=x2+x+x+one; x:=x+one; end; if now<x2 then begin x:=x-one; x2:=x2-x-x-one; end; cp[i,j]:=x2=now; inc(j,2); end; end; procedure ktcp; inline; var i:longint; begin fillchar(cp,sizeof(cp),false); for i:=1 to n do if s[i]>'0' then begin //Kiem tra cac doan do dai le fillchar(x,sizeof(x),0); fillchar(x2,sizeof(x2),0); fillchar(now,sizeof(now),0); now[0]:=1; now[1]:=so[s[i]]; x[0]:=1; x[1]:=trunc(sqrt(so[s[i]])); x2[0]:=1; x2[1]:=x[1]*x[1]; if x2=now then cp[i,i]:=true; kt(i,i+2); if i=n then continue; //Kiem tra cac doan do dai chan fillchar(x,sizeof(x),0); fillchar(x2,sizeof(x2),0); fillchar(now,sizeof(now),0); now[0]:=2; now[1]:=so[s[i+1]]; now[2]:=so[s[i]]; x[0]:=1; x[1]:=trunc(sqrt(now[2]*10+now[1])); x2[0]:=2; x2[1]:=x[1]*x[1] mod 10; x2[2]:=x[1]*x[1] div 10; if now=x2 then cp[i,i+1]:=true; kt(i,i+3); end; end; procedure solve; inline; var i,j:longint; begin fillchar(f,sizeof(f),0); f[0]:=1; for i:=1 to n do for j:=1 to i do if cp[j,i] then inc(f[i],f[j-1]); end; begin openF; readln(f1,t); init; for test:=1 to t do begin inp; ktcp; solve; ans; end; closeF; end.
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, int> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = { -1, 0, +1, 0, 1, 1, -1, -1 }; const int dc[] = { 0, +1, 0, -1, 1, -1, 1, -1 }; const int inf = (int) 1e9 + 5; const ll linf = (ll) 1e16 + 5; const int mod = (ll) (1e4 + 7 + eps); #define base 100000000 using namespace std; struct solon { int so; ll a[20]; solon(){so = 1; a[1] = 0;} solon(ll x){so = 1; a[1] = x;} }; int sosanh(solon A,solon B){ if(A.so>B.so) return 1; if(A.so<B.so) return -1; for(int i = A.so;i>=1;i--){ if(A.a[i]>B.a[i]) return 1; if(A.a[i]<B.a[i]) return -1; } return 0; } solon tong (solon A,solon B) { int du = 0; solon C; if(A.so<B.so) swap(A, B); for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0; C.so = A.so; for(int i = 1;i<=A.so;i++) { C.a[i] = (A.a[i]+B.a[i]+du)%base; du = (A.a[i]+B.a[i]+du)/base; } if(du>0) {C.so++; C.a[C.so] = du;} return C; } solon tichnho(solon A, ll k,int chuso) { solon C; ll du = 0; C.so = A.so+chuso; for(int i = 1;i<=chuso;i++) C.a[i] = 0; for(int i = chuso+1;i<=chuso+A.so;i++) { C.a[i] = (A.a[i-chuso]*k+du)%base; du = (A.a[i-chuso]*k+du)/base; } if(du>0) {C.so++; C.a[C.so] = du;} return C; } solon tich(solon A,solon B) { solon C; C.so = 1; C.a[1] = 0; for(int i = 1;i<=B.so;i++) { C = tong(C,tichnho(A,B.a[i],i-1)); } return C; } void print(solon A) { printf("%lld", A.a[A.so]); for(int i = A.so-1;i>=1;i--) printf("%08lld", A.a[i]); } solon hieu(solon A,solon B){ solon C; C.so = A.so; for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0; int du = 0; for(int i = 1;i<=A.so;i++){ C.a[i] = A.a[i]-B.a[i]-du; if(C.a[i]<0){ C.a[i]+=base; du = 1; } } while(C.a[C.so]==0) C.so--; if(C.so==0) C.so = 1; return C; } solon chia2(solon A){ int du = 0; ll x; for(int i = A.so;i>=1;i--){ x = A.a[i]; A.a[i] = (x+du*base)/2; du = x%2; } if(A.a[A.so]==0) A.so--; if(A.so==0) A.so++; return A; } int test, n; string s; bool f[105][105]; int main() { // freopen("in.txt", "r", stdin); scanf("%d",&test); for(int itest=1;itest<=test;itest++){ cin >> s; int n = s.length(); ms(f, 0); Rep(i, n) if(s[i] != '0'){ solon A, x[2], T; int u; for(int j = i; j < n; j++){ A = tong(tichnho(A, 10, 0), solon(s[j] - '0')); u = (j - i) & 1; x[u] = tichnho(x[u], 10, 0); while(true){ T = tong(x[u], solon(1)); if(sosanh(A, tich(T, T)) < 0) break; x[u] = T; } if(sosanh(A, tich(x[u], x[u])) == 0) f[i][j] = 1; } } ll res[105]; ms(res, 0); res[0] = 1; For(i, 1, n) { For(j, 1, i) if(f[j - 1][i - 1]) res[i] += res[j - 1]; // cout << i << " " << res[i] << endl; } cout << res[n] << endl; } //getch(); }
Code mẫu của khuc_tuan
import java.io.*; import java.math.*; public class Main { char[] a; long[] f; boolean[] dt; int n; boolean[] ok; boolean check(String s){ String s2=s.substring(s.length()-Math.min(4,s.length()), s.length()); if(!ok[Integer.parseInt(s2)]) return false; BigInteger b=new BigInteger(s); BigInteger x=BigInteger.ONE; BigInteger xcu=BigInteger.ZERO; while(true){ BigInteger xmoi = x.multiply(x).add(b).divide(x).divide(BigInteger.valueOf(2)); if(xmoi.equals(x) || xmoi.equals(xcu)) return xmoi.multiply(xmoi).equals(b); xcu=x; x=xmoi; } } void tinh(int i) { if(dt[i]) return; if(a[i]=='0') return; dt[i]=true; String s=""; for(int j=i;j<n;++j) { s=s+a[j]; if(check(s)) { tinh(j+1); f[i]+=f[j+1]; } } } void init() { ok=new boolean[10000]; for(int i=0;i<10000;++i) { ok[i*i % 10000] = true; } } void run() throws Exception{ BufferedReader kb=new BufferedReader(new InputStreamReader(System.in)); int st=Integer.parseInt(kb.readLine()); init(); for(int xx=0;xx<st;++xx){ a=kb.readLine().toCharArray(); n=a.length; f=new long[n+1]; dt=new boolean[n+1]; dt[n]=true; f[n]=1; tinh(0); System.out.println(f[0]); } } public static void main(String[] args) throws Exception { new Main().run(); } }
Bình luận