QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#506714#9158. 分数Misaka1617250 3192ms365364kbC++142.0kb2024-08-05 20:51:582024-08-05 20:51:59

Judging History

你现在查看的是最新测评结果

  • [2024-08-05 20:51:59]
  • 评测
  • 测评结果:50
  • 用时:3192ms
  • 内存:365364kb
  • [2024-08-05 20:51:58]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mp_ make_pair
#define pb_ push_back
#define pob_ pop_back
#define fst first
#define snd second
#define debug cout<<"********\n";
#define reset(x,y) memset(x,y,sizeof(x))
#define fi(x) freopen(x,"r",stdin)
#define fo(x) freopen(x,"w",stdout)
#define iosf ios::sync_with_stdio(0);cin.tie(0);
#define prec(x) cout<<setprecision(x);
#define prec0(x) cout<<fixed<<setprecision(x);
#define Misaka16172 sb
#define kamisako femboy

using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using uint = unsigned int;

constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ull mod1 = 1e9+7,mod9 = 998244353;

using namespace std;

template <class T>
inline void read(T &x){
    x = 0;T w = 1;
    char c = 0;
    while(!isdigit(c)){
        if(c=='-')  w = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = ((x<<3)+(x<<1))+c-'0';
        c = getchar();
    }
    x = x*w;
}
template<class T,typename ...Args>
inline void read(T &x,Args &...rest){read(x);read(rest...);}

template<class T>
inline void write(T x){
    if(!x)  return putchar('0'),void();
    else if(x<0) putchar('-'),x*=-1;
    int st[40],t = 0;
    while(x){st[++t] = x%10,x/=10;}
    while(t){putchar(st[t--]+'0');}
}

template <class T>
inline string bin(T x,int d = 0){return (((d>1)||(x>>1))?bin(x>>1,d-1):"")+to_string(x&1);}

int Test = 1,Case = 1;

unordered_map<ll,bool> vis;
constexpr ll D = 10000000000;

ll ans = 0;
int n,m;

void dfs(int u,int d){
	if(u>n || d>m || u*2>d && u<d*2 || vis.find(D*u+d)!=vis.end())	return;
	ans++,vis[D*u+d] = 1;
	dfs(d,u);
	int g = __gcd(d,u+d*2);
	dfs((u+d*2)/g,d);
	if(u/d>2 || u/d==2 && u%d){
		g = __gcd(d,u-d*2);
		dfs((u-d*2)/g,d);
	}
}

void solve(){
    read(n,m);
    dfs(1,2);
    cout<<ans;
}

int main(){
//  read(Test);
    for(;Case<=Test;++Case) solve();
    return 0;
}

详细


Pretests

Pretest #1:

score: 5
Accepted
time: 0ms
memory: 3616kb

input:

99 99

output:

406

result:

ok 1 number(s): "406"

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 3780kb

input:

98 97

output:

405

result:

ok 1 number(s): "405"

Pretest #3:

score: 5
Accepted
time: 0ms
memory: 3576kb

input:

99 96

output:

396

result:

ok 1 number(s): "396"

Pretest #4:

score: 5
Accepted
time: 2ms
memory: 3996kb

input:

995 977

output:

11153

result:

ok 1 number(s): "11153"

Pretest #5:

score: 5
Accepted
time: 2ms
memory: 3928kb

input:

991 990

output:

11220

result:

ok 1 number(s): "11220"

Pretest #6:

score: 5
Accepted
time: 2ms
memory: 4184kb

input:

976 968

output:

10900

result:

ok 1 number(s): "10900"

Pretest #7:

score: 0
Wrong Answer
time: 29ms
memory: 12712kb

input:

7602 7864

output:

210506

result:

wrong answer 1st numbers differ - expected: '215706', found: '210506'

Pretest #8:

score: 5
Accepted
time: 30ms
memory: 12980kb

input:

7959 7735

output:

220256

result:

ok 1 number(s): "220256"

Pretest #9:

score: 5
Accepted
time: 35ms
memory: 12788kb

input:

7878 7863

output:

221162

result:

ok 1 number(s): "221162"

Pretest #10:

score: 5
Accepted
time: 29ms
memory: 12888kb

input:

7788 7658

output:

215323

result:

ok 1 number(s): "215323"

Pretest #11:

score: 0
Wrong Answer
time: 3082ms
memory: 351124kb

input:

95399 99767

output:

8018282

result:

wrong answer 1st numbers differ - expected: '8285295', found: '8018282'

Pretest #12:

score: 0
Wrong Answer
time: 3192ms
memory: 361656kb

input:

98051 99642

output:

8341748

result:

wrong answer 1st numbers differ - expected: '8439713', found: '8341748'

Pretest #13:

score: 0
Wrong Answer
time: 3058ms
memory: 351920kb

input:

95624 96007

output:

8045076

result:

wrong answer 1st numbers differ - expected: '8068127', found: '8045076'

Pretest #14:

score: 5
Accepted
time: 3171ms
memory: 363848kb

input:

99208 98047

output:

8412610

result:

ok 1 number(s): "8412610"

Pretest #15:

score: 0
Time Limit Exceeded

input:

997417 967722

output:


result:


Pretest #16:

score: 0
Time Limit Exceeded

input:

987807 956529

output:


result:


Pretest #17:

score: 0
Time Limit Exceeded

input:

971654 984345

output:


result:


Pretest #18:

score: 0
Time Limit Exceeded

input:

7892259 7983727

output:


result:


Pretest #19:

score: 0
Time Limit Exceeded

input:

7937869 29796968

output:


result:


Pretest #20:

score: 0
Time Limit Exceeded

input:

29717543 29510173

output:


result:



Final Tests

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3588kb

input:

96 98

output:

386

result:

wrong answer 1st numbers differ - expected: '396', found: '386'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3584kb

input:

100 99

output:

408

result:

ok 1 number(s): "408"

Test #3:

score: 5
Accepted
time: 0ms
memory: 3604kb

input:

99 99

output:

406

result:

ok 1 number(s): "406"

Test #4:

score: 5
Accepted
time: 0ms
memory: 4020kb

input:

963 951

output:

10634

result:

ok 1 number(s): "10634"

Test #5:

score: 0
Wrong Answer
time: 2ms
memory: 4148kb

input:

958 974

output:

10642

result:

wrong answer 1st numbers differ - expected: '10795', found: '10642'

Test #6:

score: 0
Wrong Answer
time: 1ms
memory: 4016kb

input:

966 990

output:

10786

result:

wrong answer 1st numbers differ - expected: '11003', found: '10786'

Test #7:

score: 5
Accepted
time: 31ms
memory: 13168kb

input:

7958 7947

output:

224482

result:

ok 1 number(s): "224482"

Test #8:

score: 0
Wrong Answer
time: 28ms
memory: 12732kb

input:

7623 7730

output:

211290

result:

wrong answer 1st numbers differ - expected: '213444', found: '211290'

Test #9:

score: 5
Accepted
time: 31ms
memory: 12920kb

input:

7845 7783

output:

218916

result:

ok 1 number(s): "218916"

Test #10:

score: 5
Accepted
time: 26ms
memory: 12888kb

input:

7881 7773

output:

219451

result:

ok 1 number(s): "219451"

Test #11:

score: 5
Accepted
time: 3178ms
memory: 365364kb

input:

99414 98698

output:

8465217

result:

ok 1 number(s): "8465217"

Test #12:

score: 5
Accepted
time: 3142ms
memory: 358232kb

input:

98249 96148

output:

8237486

result:

ok 1 number(s): "8237486"

Test #13:

score: 5
Accepted
time: 3166ms
memory: 361124kb

input:

99003 96832

output:

8324931

result:

ok 1 number(s): "8324931"

Test #14:

score: 5
Accepted
time: 3175ms
memory: 358196kb

input:

98266 96030

output:

8231065

result:

ok 1 number(s): "8231065"

Test #15:

score: 0
Time Limit Exceeded

input:

968207 958885

output:


result:


Test #16:

score: 0
Time Limit Exceeded

input:

959846 998397

output:


result:


Test #17:

score: 0
Time Limit Exceeded

input:

965821 972280

output:


result:


Test #18:

score: 0
Time Limit Exceeded

input:

7855098 7962479

output:


result:


Test #19:

score: 0
Time Limit Exceeded

input:

7841076 29648718

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

29365129 29012208

output:


result: