分治，1875C - Jellyfish and Green Apple

本文主要是介绍分治，1875C - Jellyfish and Green Apple，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1875C - Jellyfish and Green Apple

---

二、解题报告

1、思路分析

n 个苹果分给m个人

相当于先给每人分n / m个，然后把n % m个苹果分给m个人

如果n % m / gcd(n % m, m) 不是2的幂，则无解

否则，我们可以递归分治，也可以循环求解

n 不断 * 2 再 % m，累加贡献

2、复杂度

时间复杂度：O(logN) 空间复杂度：O(1)

3、代码详解

 ​

#include <bits/stdc++.h>using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 1'000'000'007;void solve() {int n, m;std::cin >> n >> m;n %= m;int g = std::gcd(n, m);n /= g, m/= g;if (m & (m - 1)) {std::cout << "-1\n";return;}i64 res = 0;while (n)res += n, n = n * 2LL % m;std::cout << res * g << '\n';
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();int main () {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifint T = 1;std::cin >> T;while (T --)solve();return 0;
}

这篇关于分治，1875C - Jellyfish and Green Apple的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---