本文主要是介绍ABC#227，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A
题目大意
n个元素（编号1，2，…），从编号为a的元素开始数起（循环计数），数到k的元素是哪一个。
#include <iostream>
using namespace std;int main()
{int n, k, a;cin >> n >> k >> a;int res = (a + k - 1) % n;if (res == 0) res = n;cout << res;return 0;
}
C
题目大意
给定一个数N，求出满足： a ≤ b ≤ c 且 a × b × c ≤ N a ≤ b ≤ c \ 且\ a\times b\times c ≤N a≤b≤c 且 a×b×c≤N的三元组 ( a , b , c ) (a,b,c) (a,b,c)的个数。
naive方法（TLE）
int n, cnt = 0;
cin >> n;
for (int i = 1; i <= n; i ++)for (int j = i; j <= n; j ++)for (int k = j; k <= n; k ++)if (i * j * k <= n) cnt ++;
cout << cnt;
简单优化
由题意可确定a，b，c的范围分别为： 1 ≤ a ≤ n 3 ， a ≤ b ≤ N a ， b ≤ c ≤ N a b 1≤a≤\sqrt[3]{n}，a\le b\le \sqrt{\frac{N}{a}}，b\le c\le\frac{N}{ab} 1≤a≤3n，a≤b≤aN，b≤c≤abN
仍然TLE
int n, cnt = 0;
cin >> n;
for (int i = 1; i*i*i <= n; i ++)for (int j = i; j*j <= n/i; j ++)for (int k = j; k <= n/i/j; k ++)if (i*j*k <= n) cnt ++;
cout << cnt;
注意到：当a，b取定之后，c的范围确定，因此此时c的可取值的个数就随之确定，为 [ N a b ] − b + 1 [\frac{N}{ab}]-b+1 [abN]−b+1
因此程序可以改进为：
O ( n 2 3 ) O(n^{\frac{2}{3}}) O(n32)
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;int main()
{LL n, cnt = 0;cin >> n;for (LL i = 1; i*i*i <= n; i ++)for (LL j = i; j*j <= n/i; j ++)cnt += n/i/j - j + 1;cout << cnt;return 0;
}
这篇关于ABC#227的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
