嵌套while循环解法超时 如何优化降低时间复杂度

题目规则：

• 第一行输入测试用例总数t
• 每组用例输入两个整数a、b，需按顺序对a执行第i次操作：
  • i为奇数时，a += 1
  • i为偶数时，a += 2
• 若a能通过若干次操作恰好等于b，输出YES，否则输出NO

原有逐次模拟的代码时间复杂度为O(d)（d为a和b的差值），当d数值较大（如1e9级别）时，单组用例需要循环数亿次，必然触发时间超限。

不需要逐次模拟操作，通过数学规律可以做到O(1)常数时间判断：

1. 所有操作都是给a加正整数，因此如果b < a（即差值d = b - a < 0），a永远不可能等于b，直接输出NO。
2. 观察操作增量规律：每两次操作为一个周期，总增量为1+2=3。统计执行k次操作的总增量：
   • 当k为偶数（k=2m）：总增量为3*m，对3取余结果为0
   • 当k为奇数（k=2m+1）：总增量为3*m +1，对3取余结果为1
3. 也就是说，所有可达的差值d对3取余的结果只能是0或1，不可能为2。

最终判断逻辑：

• d < 0 → 输出NO
• d %3 == 0 或 d%3 ==1 → 输出YES
• d%3 ==2 → 输出NO

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // 关闭cin同步，解绑cin和cout，提升大输入量下的IO速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, a, b;
    cin >> t;
    while (t--)
    {
        cin >> a >> b;
        int d = b - a;
        if (d < 0 || d % 3 == 2)
        {
            cout << "NO\n";
        }
        else
        {
            cout << "YES\n";
        }
    }
    return 0;
}

优化后代码无论a、b差值多大，单组用例都只需要一次计算即可得到结果，完全不会出现循环超时问题，IO优化也能避免大测试用例输入阶段的耗时。

内容的提问来源于stack exchange，提问作者Yuvraj。