沐咕 @ 2024-11-08 21:34:30
#include <bits/stdc++.h>
using namespace std;
long long a, b;
set<long long> s;
int main()
{
cin >> a >> b;
s.insert(a);
s.insert(b);
long long x = a, y = b;
while (true)
{
if (s.find(abs(y - x)) != s.end())
break;
s.insert(abs(y - x));
x = y;
y = abs(y - x);
}
cout << s.size() << endl;
return 0;
}by 沐咕 @ 2024-11-08 21:48:48
@Louis 两个都 T 了（
by Argon_Cube @ 2024-11-08 21:48:59
@Louis s.find(make_pair(x,y))!=s.end()
by __Louis__ @ 2024-11-08 21:50:15
搞错了重新来。
#include <bits/stdc++.h>
using namespace std;
long long a, b;
set<long long> s;
int main()
{
cin >> a >> b;
s.insert(a);
s.insert(b);
long long x = a, y = b;
while (true)
{
if(x==0||y==0)
break;
s.insert(abs(y - x));
long long tx = x;
x = y;
y = abs(y - tx);
}
cout << s.size() << endl;
return 0;
}很明显这个有问题了，因为这样肯定T飞，所以直接模拟是错的。
by 沐咕 @ 2024-11-08 21:51:00
@Louis 不，新代码 MLE，90分了（
qwq
by __Louis__ @ 2024-11-08 21:51:00
所以这到题建议还是转到gcd上要好一点qwq。
by ran_qwq @ 2024-11-08 21:51:08
一个正确性对的程序：
#define il inline
#define ui unsigned int
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define ldb long double
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define fir first
#define sec second
#define gc getchar
#define pc putchar
#define mst(a,x) memset(a,x,sizeof a)
#define mcp(a,b) memcpy(a,b,sizeof b)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pct __builtin_popcount
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f,MOD=998244353;
const ll INFll=0x3f3f3f3f3f3f3f3f;
il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il void wr(int x) {if(x==INT_MIN) return printf("-2147483648"),void(); if(x<0) return pc('-'),wr(-x); if(x<10) return pc(x+'0'),void(); wr(x/10),pc(x%10+'0');}
il void wrll(ll x) {if(x==LLONG_MIN) return printf("-9223372036854775808"),void(); if(x<0) return pc('-'),wrll(-x); if(x<10) return pc(x+'0'),void(); wrll(x/10),pc(x%10+'0');}
il void wr(int x,char *s) {wr(x),printf("%s",s);}
il void wrll(ll x,char *s) {wrll(x),printf("%s",s);}
il int vmod(int x) {return x>=MOD?x-MOD:x;}
il int vadd(int x,int y) {return vmod(x+y);}
il int vsub(int x,int y) {return vmod(x-y+MOD);}
il int vmul(int x,int y) {return 1ll*x*y%MOD;}
il int qpow(int x,int y) {int res=1; for(;y;y>>=1,x=vmul(x,x)) if(y&1) res=vmul(res,x); return res;}
il void cadd(int &x,int y) {x=vmod(x+y);}
il void csub(int &x,int y) {x=vmod(x-y+MOD);}
il void cmul(int &x,int y) {x=vmul(x,y);}
il void cmax(int &x,int y) {x<y&&(x=y);}
il void cmaxll(ll &x,ll y) {x<y&&(x=y);}
il void cmin(int &x,int y) {x>y&&(x=y);}
il void cminll(ll &x,ll y) {x>y&&(x=y);}
void QwQ() {
ll a=rdll(),b=rdll();
#define pll pair<ll,ll>
set<ll> s={a,b}; set<pll> t={{a,b}};
while(1) {
ll tmp=a; a=b,b=abs(tmp-b),s.insert(b);
if(t.count({a,b})) break; t.insert({a,b});
}
wr(s.size(),"\n");
}
signed main() {
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
int T=1; while(T--) QwQ();
}
by __Louis__ @ 2024-11-08 21:51:27
MLE 飞应该是一样的，也是模拟导致的qwq
by __Louis__ @ 2024-11-08 21:52:02
@ran_qwq 你这肯定也MLE啊
by ran_qwq @ 2024-11-08 21:52:17
模拟会把set搞的特别大，你不MLE谁MLE
by DDD_et @ 2024-11-08 21:52:56
@沐咕
但是