codeforce每日一题链接

题目描述

给你n，k，你要从0开始，怎样不是k的倍数的距离才能走到n，距离可以为负。

样例

输入样例1

3
10 2
10 3
3 4

输出样例1

2
7 3
1
10
1
3

算法1

(暴力枚举) $O(n^2)$

直接暴力枚举就好了。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

inline void solve()
{
    cin>>n>>m;
    if(n==1) cout<<1<<endl<<1<<endl;
    else if(n%m!=0) cout<<1<<endl<<n<<endl;
    else
        for(int i=-1e4;i<=1e4;i++){
        if(i%m!=0 && (n-i)%m!=0){
            cout<<2<<endl;
            cout<<i<<' '<<n-i<<endl;
            return;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}

算法

(思维) $O(1)$

可以输出1和n-1.

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

inline void solve()
{
    cin>>n>>m;
    if(n==1) cout<<1<<endl<<1<<endl;
    else if(n%m!=0){
        cout<<1<<endl<<n<<endl;
    }else{
        cout<<2<<endl;
        cout<<1<<" "<<n-1<<endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}