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;
}
直接判 x % k 不是更简洁更快吗
可以的,最后一个else可以直接输出1和n-1