这是一道值得思考的题目

进阶O(n)答案

这题数据范围很小，O(n^2),O(n^3)，甚至是 O(n^4)都能过，不过我们依然要考虑进阶解法。 下面是代码：

（最好自己研究懂，想不通看解析）（已AC）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int sum=0,n;
    cin>>n;
    for (int i=2;i<=n*2;i++)
    {/*遍历从2到n*2的所有数
（为什么是n*2呢？）
      */
        if (i%3==0 || i%7==0)
        {//如果i能被3/7整除。
            if (i<=n+1)
                sum+=(i-1)/2;
            //为什么要这么加？
            else//如果i>n
                sum+=((n+1)-(i-(n+1))-1)/2;
            //又为什么这么加？
        }
    }
    cout<<sum;
    return 0;
}

解析

这段代码的核心思路就是把X+Y当做一个数遍历

• 我们可以发现，姐妹数对根本就是一个迷惑项，所有的条件判断多是建立在X+Y上的，根本不用遍历X和Y。
• 这也就能解释循环为什么是2—n* 2了，因为X和Y最小都是1和为2，最大都是n和为n* 2，这也就是遍历2—n*2的原因。
• 这个理解了，后面的判断条件也好理解了。因为X+Y就是i嘛，所以直接判断即可。
• 最难的部分就是==sum什么条件？满足条件加几？==也就是X+Y为i时，X和Y有几种取法
• 还有就是怎么加？不过这也就是一道，偏难小学找规律数学题的水平，做着道题本身不难，难的是，把它转换成找规律题目题目的能力。
• 我们可以用解小学找规律题的办法解，回忆一下，不就是，列出1，2，3，4的数，把1对应的，2对应的，3对应的写到下面，看看i为几时，X和Y有几种取法加到sum里？那我们也列出来。

• 注：前提条件是n>10;
• 列出来后，很明显第i个数有(i-1)/2种取法。这就是第一个算式的来历。
• 那第二个算式又式怎么回事？不要忘了，X和Y最大只能取到n，上面这个算式是假定X和Y最大能取到i-1，如i为n+2时，那上面算式就不成立了。就要新定义算式这也解释了为什么判断条件是n+1。
• 依然是上面这个方法，列出来。
• 假设n是7

• 注意，题目要求X和Y不同，所以14，的两个7，是不行的，14是取不到一个数的。
• 我们可以看出，n+1后的数，与n+1前的数取得值是相对的。我们可以据此得出算式==((n+1)-(i-(n+1))-1)/2==，其实就是先求出对称的数，之后求出对称的数的值。
• 这样，一段O(n)的代码就写好了。

带解析代码（求赞）：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int sum=0,n;
    cin>>n;
    for (int i=2;i<=n*2;i++)
    {//因为i代表X+Y，所以最大是n*2
        if (i%3==0 || i%7==0)
        {
            if (i<=n+1)//如果在前半部分
                sum+=(i-1)/2;//根据规律得出
            else
                sum+=((n+1)-(i-(n+1))-1)/2;
                //根据规律
        }
    }
    cout<<sum;//输出答案。
    return 0;
}

题解后作业。

相信聪明的同学也看得出来，这段代码是可以O(1)的，也不是很难，就留做课后作业了，又想出来的可以发代码解析在评论区。下面我给一点思路：

• i%3=0 的数和 i%7=0 的数，分开求。 *参考 以上我们找的规律，将全部数进行等差数列求和，其实就是i%1=0的数的和，与 i%3=0 的数和 i%7=0 的数 实际上差不多，只不过在计算方式中要多几个变量。
• 可以先用等差数列求出i%1=0的数，以此次往后分别推出i%3=0的数和i%7=0的数，求和。
• 注意：i%3=0的数和i%7=0的数，会重合，所以应该加上后再减去i%21=0的数。

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int i, j, s = 0;
    for (i = 1; i < n; i++)
    {
    	for (j = i + 1; j <= n; j++)
        {
    		if ((i + j) % 3 == 0 || (i + j) % 7 == 0)
            {
    			s++;
			}
		}
	}
    cout << s;
}//已AC

这道题很简单，就是要注意数对重复的情况，比如 (1,2) 和 (2,1)，还要保证数对中的两个数不能相同 (都是根据题目要求)，要想实现这两个目标，循环变量j只要开始设定成i+1就行了(也是花了十多分钟才想到这个规律)，真是一举两得，好了，废话不多说，上代码！

已AC，请放心食用( •̀ ω •́ )✧

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, num = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if ((i + j) % 3 == 0 || (i + j) % 7 == 0)
            {
                num++;
            }
        }
    }
    cout << num;
    return 0;
}

看完后点个赞再走呗

彩蛋：

其实只要输出 1354 就行了，因为题目只有一个样例

好了，现在让我们有请下一位题解选手

简单

#include <bits/stdc++.h>
using namespace std;
int n,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if((i+j)%3==0||(i+j)%7==0)
                ans++;
        }
    }
    cout<<ans;
    return 0;
}

本题真正答案：

#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin>>n;
    cout<<"1354";
    return 0;
}

#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			if ((i + j) % 3 == 0 || (i + j) % 7 == 0)
			{
				sum++;
			}
		}
	}
	cout << sum;
	return 0;
}