有N本书，排成一行。珂珂发现从前向后看，从第1本开始，间隔是3的书都是她喜欢的，也就是第1、4、7、10…本书。乐乐发现从后向前看，从最后一本开始，间隔是4的书都是他喜欢的。 请问有多少本书是他们共同爱好的？ 输入格式 第一行1个正整数：N，范围在[1,10000]。 输出格式 一个整数。 输入/输出例子1 输入： 100 输出： 9 用cpp

<think>题目：有N本书，排成一行。珂珂喜欢的书是第1、4、7、10...本（从前往后，间隔3，即每3本取第一本，起始位置为1）。 乐乐喜欢的书是：从后向前看，从最后一本开始，间隔4的书（即每4本取一本，从最后一本开始）。 问两人共同喜欢的书有多少本？ 分析： 珂珂喜欢的书的位置：1, 4, 7, 10, ... 即位置序列为：a_k = 1 + 3*k (k=0,1,2,...) 且 a_k <= N 乐乐喜欢的书的位置：从后往前，间隔4。我们设最后一本书的位置为1（从后往前数），那么乐乐喜欢的书在从后往前的序列中是：1,5,9,... 但是我们需要将其转换为从前往后的位置（假设书的位置从1到N，1是开头，N是结尾）。 从后往前的位置与从前往后的位置对应关系：如果从前往后位置为x，那么从后往前的相对位置就是N-x+1。 乐乐喜欢的位置在从后往前的序列中是：1, 5, 9, ... 即 b_j = 1 + 4*j (j=0,1,2,...) 且 b_j <= N（从后往前的位置不能超过总书数，即b_j<=N）。 那么对应到从前往后的位置：x = N - (b_j - 1) = N - b_j + 1? 不对，因为b_j是从后往前的位置（最后一个是1，倒数第二个是2，...），所以从前往后的位置应该是：x = N - (b_j - 1) = N - b_j + 1? 实际上：从后往前的位置为p，则对应的从前往后的位置是：N - p + 1。 所以，乐乐喜欢的书在从前往后的位置为：x = N - (1+4*j) + 1 = N - 4*j。 验证：例如N=10，乐乐喜欢的书在从后往前的第1本（即最后一本）对应从前往后位置10，第5本（从后往前）对应从前往后位置10-5+1=6，第9本对应2。 所以乐乐喜欢的书的位置：10, 6, 2。即序列：x_j = N - 4*j (j=0,1,2,...) 且 x_j>=1。 问题转化为：求同时满足以下两个条件的x的个数： x = 1 + 3*k (k为整数，且0<=k, 1+3*k<=N) x = N - 4*j (j为整数，且0<=j, N-4*j>=1) 即：1+3*k = N-4*j => 3*k + 4*j = N-1 我们需要求非负整数解(k, j)的个数，且满足： 1+3*k <= N => 3*k <= N-1 => k <= (N-1)/3 N-4*j>=1 => 4*j <= N-1 => j <= (N-1)/4 因此，问题变成：求方程 3*k + 4*j = N-1 的非负整数解(k, j)的个数，其中k<=floor((N-1)/3), j<=floor((N-1)/4)。 但是，我们也可以直接枚举k或j？由于N最大10000，但是我们可以用数学方法。 注意：这是一个线性丢番图方程。我们可以先求出一组特解，然后求通解，再在范围内统计解的个数。 然而，更简单的方法：固定一个变量，枚举另一个变量。由于N最大10000，我们可以枚举k（k的范围大约是0到(N-1)/3，即最大3333）或者枚举j（j的范围0到(N-1)/4，即2500），都是可以接受的。 但是，我们也可以不枚举，而是用数学公式。 方法1：枚举k，然后检查是否存在非负整数j满足条件。 k从0到floor((N-1)/3)，对于每个k，计算：j = (N-1-3*k)/4 要求：j是非负整数，且j<=floor((N-1)/4) （其实只要j是非负整数且满足j<=floor((N-1)/4)即可，但是由等式可知，如果j是整数，那么自然满足j=(N-1-3*k)/4，而由k的范围，3*k<=N-1，所以j>=0，然后我们只需要检查j是否为整数并且j<=floor((N-1)/4)？实际上，由于j=(N-1-3*k)/4，当k增大时，j减小，所以j的最大值在k=0时取得，为(N-1)/4，因此只要j是整数且非负（已经满足）即可，因为j自动小于等于(N-1)/4，但注意j必须是整数。 因此，我们只需要判断(N-1-3*k)是否非负且能被4整除。 方法2：枚举j，然后检查k：k=(N-1-4*j)/3，要求k是非负整数且k<=floor((N-1)/3)。 两种方法都可以，这里我们选择枚举k（因为k的范围比j略大一点，但差别不大，都可以）。 注意：当N=1时，方程变为：3k+4j=0，此时k=0,j=0是唯一解，且x=1（珂珂：1在序列中；乐乐：从后往前第一本也是1，所以1是共同喜欢的），所以答案是1。 但是，我们验证一下：N=1，珂珂喜欢的书：位置1（因为1<=1，所以有1）。乐乐喜欢的书：从后往前第一本是1（因为N=1，所以只有1本，从后往前第一本也是1），所以1是共同喜欢的。所以解为1。 因此，算法步骤： 1. 读入N。 2. 如果N=0，则输出0（但题目范围[1,10000]）。 3. 初始化计数count=0。 4. 枚举k，从0开始，直到3*k<=N-1（即k<= (N-1)/3）： 令 rem = N-1-3*k 如果 rem <0，则跳出循环。 如果 rem %4 ==0，则j=rem/4，此时j是非负整数（因为rem>=0），那么这一组(k,j)就是一组解，count++。 5. 输出count。 但是，我们也可以反过来想：方程3k+4j=N-1，实际上就是求(N-1)是否可以表示为3和4的非负整数线性组合，且解的组数。 但是，我们枚举k的方法已经足够高效。 验证例子：输入100，输出9。 计算：N-1=99 枚举k：k从0到33（因为3*33=99<=99） 当k=0: rem=99, 99%4=3 -> 不整除 当k=1: rem=96, 96%4=0 -> 整除，j=24 -> 解：k=1,j=24 -> 共同书位置：1+3*1=4，或者100-4*24=100-96=4 -> 正确。 当k=2: rem=93 -> 93%4=1 -> 不行 当k=3: rem=90 -> 90%4=2 -> 不行 当k=4: rem=87 -> 87%4=3 -> 不行 当k=5: rem=84 -> 84%4=0 -> 解，j=21 -> 位置：1+3*5=16，100-4*21=16 -> 正确。 ... 直到k=33: rem=99-99=0 -> 0%4=0 -> 解，j=0 -> 位置：1+3*33=100，100-4*0=100 -> 正确。 我们需要统计有多少个k使得rem%4==0。 观察：rem = 99-3*k = 3*(33-k) 要能被4整除，即3*(33-k)是4的倍数。 因为3和4互质，所以33-k必须是4的倍数。即33-k是4的倍数，也就是k=33,29,25,...,1 即k=33-4*t (t=0,1,2,...)，且k>=0。 所以k的取值：从33开始，每次减4，直到1（因为33,29,...,1）共9个数（33,29,25,21,17,13,9,5,1）。 所以有9个解。因此输出9。 因此，我们写程序枚举k，然后判断(N-1-3*k)是否能被4整除且非负（非负在循环条件已经保证了）。 代码实现： 注意：当N=1时，N-1=0，那么k=0时，rem=0，0%4==0 -> 成立，所以count=1，正确。 但是，我们也可以直接计算：k需要满足 (N-1-3*k)>=0 且 (N-1-3*k) mod 4 ==0。 因此，我们写代码： 考虑边界：N=1，k从0开始，k=0: 3*0=0<=0 -> 进入循环，rem=0，0%4==0 -> count=1。 所以代码： 注意：由于k是整数，所以循环条件：k从0到(N-1)/3（取整），但我们可以用k<= (N-1)/3，因为整数除法会自动取整，但为了避免浮点，我们写成：k从0到(N-1)/3（整数除法）？但是C++中整数除法是向下取整，所以我们可以用： for (int k=0; k<=(N-1)/3; k++) // 因为当(N-1)不能被3整除时，这样写也是安全的，因为k是整数，所以k最大就是floor((N-1)/3) 但是，我们也可以写成：for (int k=0; 3*k<=N-1; k++) 这样更清晰。 代码： 注意：如果N-1-3*k是负数，循环条件已经避免了（因为3*k<=N-1，所以非负）。 因此，程序如下： 但是，我们也可以不枚举，直接计算解的个数： 我们要求：3*k <= N-1 且 (N-1-3*k)是4的非负倍数，即 (N-1-3*k) mod 4 ==0 且 (N-1-3*k)>=0。 设 d = N-1-3*k，则 d>=0 且 d mod4==0。 即：N-1-3*k ≡ 0 (mod 4) => 3*k ≡ N-1 (mod 4) => k ≡ (N-1)*3^{-1} mod 4 （3在模4下的逆元是3，因为3*3=9≡1 mod4） 所以 k ≡ (N-1)*3 mod4 => k ≡ (N-1)*3 mod4 即 k ≡ 3*(N-1) mod4 （注意：3^{-1} mod4=3） 所以k必须满足：k mod4 = (3*(N-1)) mod4 且 0<=k<=floor((N-1)/3) 那么满足条件的k的个数就是：在区间[0, floor((N-1)/3)]内，模4余数为r（r= (3*(N-1))%4）的整数个数。 但是，我们还需要注意：当N-1-3*k>=0，且k在区间内，并且模4余r。 那么如何计算个数？设最小满足条件的k0：在[0,3]中满足k0≡r (mod4)的最小非负整数k0（即r本身，但r在0~3之间），然后下一个就是k0+4, k0+8, ... 直到不超过M=floor((N-1)/3)。 所以个数为：floor((M - k0)/4) + 1 （如果k0<=M，否则为0） 但是，我们也可以这样：个数 = ((M - r) / 4) + 1 ？不对，因为r是余数，但k0不一定等于r，因为r可能大于M？不对，r在0~3，而k0=r（如果r<=M）？不一定，因为r可能大于M吗？不会，因为r在0~3，而M>=0，所以如果M>=r，那么最小符合条件的k0=r（因为r在[0,3]内，且r<=M），那么下一个就是r+4，直到不超过M。所以个数为：1 + (M - r) / 4 （整数除法，向下取整）？不对，因为r+4*i<=M，所以i的最大值就是0到(M-r)/4（取整），所以个数为：((M - r) / 4) + 1 （如果M>=r，否则为0） 但是，我们还需要验证：比如M=33, r=1（即3*(N-1) mod4=1，比如N=100，则N-1=99，3*99=297，297 mod4=297%4=297-74*4=297-296=1，所以r=1）。那么个数：k0=1，然后5,9,...,33。33-1=32，32/4=8，8+1=9。正确。 但是，如果r=0，那么k0=0，然后4,8,...,直到不超过M。个数：M/4（整除）？不对，因为0,4,8,..., 最大不超过M，个数为：M/4 + 1（因为0也算）？不对，比如M=3，r=0，那么k0=0，下一个是4（大于3），所以只有0。所以个数为：0/4+1=1？不对，应该是1。公式：个数 = (M/4) + 1 （当r=0）？不对，因为M=3，那么0,4（不行）->所以只有0，个数为1。但是用公式：个数= (M - r)/4 +1 = (3-0)/4+1=0+1=1，正确。M=4，r=0：则k=0,4 -> 2个，公式：(4-0)/4+1=1+1=2。正确。 所以公式：如果M<r，则0个；否则，个数为：1 + (M - r)/4 （整数除法，向下取整）？不对，应该是：1 + (M - r) / 4 （整数除法，这里除法是整除，即商向下取整）？但是C++中整数除法是向0取整？不对，对于非负数，是向下取整。所以可以。 因此，我们也可以不用枚举，直接计算： M = (N-1)/3; // 整数除法，向下取整 r = (3*(N-1)) % 4; // 注意：3*(N-1)可能很大，但模4，我们可以用(N-1)%4，然后再乘3再模4：r = ( (N-1)%4 * 3 ) % 4; if (M < r) count = 0; else count = (M - r)/4 + 1; 但是，注意：r的取值范围是0~3，而M>=0。 验证：N=1: M=(0)/3=0, r=(0%4)*3%4=0 -> 0<0? 不成立，所以M>=r -> count=(0-0)/4+1=0+1=1，正确。 N=100: M=99/3=33, r= (99%4)*3 %4 = (3*3)%4=9%4=1 -> count=(33-1)/4+1=32/4+1=8+1=9，正确。 但是，我们还需要验证其他情况，比如N=2： 珂珂：位置1（因为1<=2，位置2：1+3=4>2，所以只有1） 乐乐：从后往前：位置1（最后一本）对应位置2，位置5（不存在）-> 所以乐乐喜欢位置2（因为从后往前第一本是2，第二本是1，但间隔4，所以只有第一本，即位置2） 共同喜欢的：位置1和位置2不同，所以没有共同喜欢的。所以输出0。 用公式：M=(2-1)/3=1/3=0（整数除法），r=( (1)%4 *3 )%4= (1*3)%4=3 -> 因为M=0<3，所以count=0，正确。 再验证N=5： 珂珂：1,4 乐乐：从后往前：位置1（最后一个是5），位置5（不存在）-> 所以乐乐只有5。然后间隔4，所以下一本是5-4=1（从后往前的位置：1（5），5（1））-> 不对，乐乐喜欢的书：从后往前每4本取一本，所以第一本是5（从后往前位置1），然后下一个位置是1+4=5，但是5>5（书只有5本，从后往前位置最大是5？不对，从后往前位置：5是第1本，4是第2本，3是第3本，2是第4本，1是第5本。乐乐取间隔4：从1开始，取1（即最后一本，位置5），然后1+4=5，但5>5（总书数5）？不对，从后往前位置，我们定义最后一本是1，倒数第二本是2，倒数第三本是3，倒数第四本是4，倒数第五本是5。所以乐乐取：1,5（因为1+4=5，5<=5，所以有位置5，对应从前往后位置：5-5+1=1？不对，我们之前定义：从前往后位置x对应的从后往前位置是N-x+1。所以从后往前位置p对应的从前往后位置是x=N-p+1。所以p=1->x=5, p=5->x=1。所以乐乐喜欢的书：位置5和1。所以共同喜欢的：1和5，而珂珂喜欢1和4，所以共同喜欢1。所以答案是1。 用公式：N=5，M=(5-1)/3=4/3=1（整数除法），r=(4%4*3)%4= (0*3)%4=0 -> count=(1-0)/4+1=1/4+1=0+1=1，正确。 但是，我们之前推导的公式：x=1+3*k = N-4*j -> 3k+4j=N-1 当N=5：3k+4j=4，非负整数解：k=0,j=1（0+4=4）-> 对应位置1（k=0:1+0=1）和k=1:1+3=4，但3*1+4*j=3+4j=4 -> 4j=1，j不是整数。所以只有k=0,j=1一组解。所以共同的书位置1。 所以，我们可以用直接计算的方法，避免枚举。 但是，注意：当N-1为负数（即N=0）时，但题目N>=1，所以不考虑。 因此，程序如下： 但是，注意：M=(N-1)/3，在C++中整数除法是截断（向0取整）？对于非负数，是向下取整（即舍去小数部分）。例如：4/3=1，1/3=0。 所以，我们写： int M = (N-1)/3; // 因为N-1>=0，所以整数除法向下取整。 int r = ( (N-1) % 4 * 3 ) % 4; // 计算r = (3*(N-1)) mod4 if (M < r) count = 0; else count = (M - r) / 4 + 1; 但是，注意：当N-1=0（即N=1）时，M=0，r=(0%4*3)%4=0，所以count= (0-0)/4+1=1。 但是，我们还要考虑：r可能为负数吗？不会，因为模4的结果是0,1,2,3。 所以，我们输出count。 但是，我们也可以写枚举的方法，因为N最大10000，枚举k最多3334次，完全可以接受。 为了保险，我们写枚举的方法。 代码（枚举法）： 步骤： int count = 0; for (int k=0; 3*k <= N-1; k++) { int rem = N-1-3*k; if (rem % 4 == 0) // 因为rem>=0，所以只要判断整除 count++; } cout << count << endl; 测试：N=100 -> count=9，正确。 但是，注意：rem可能很大，但整数取模没问题。 所以，我们写枚举法。 但是，我们也可以考虑用数学公式法，因为公式法更高效（常数时间）。 两种方法都可以，这里我们写两种，但题目要求代码，我们写一种即可（枚举法简单明了）。 代码： 注意：当N=0时，但题目范围[1,10000]，所以不考虑。 因此，我们写： #include <iostream> using namespace std; int main() { int N; cin >> N; int count = 0; // 枚举k，满足 3*k <= N-1 for (int k=0; 3*k <= N-1; k++) { int rem = N-1 - 3*k; if (rem % 4 == 0) count++; } cout << count << endl; return 0; } 测试： N=1: rem=0 -> 0%4==0 -> count=1，输出1。 N=2: rem=1 -> 1%4!=0 -> 然后k=1: 3*1=3>1 -> 循环结束，count=0，输出0。 N=5: rem=4 -> 4%4==0 -> count=1；然后k=1: rem=4-3=1 -> 1%4!=0；k=2: 3*2=6>4 -> 结束。所以count=1，正确。 但是，我们也可以优化：当rem<0时跳出，但循环条件已经保证了。 所以，提交这个代码。 但是，我们也可以写公式法，公式法更高效（O(1)）: #include <iostream> using namespace std; int main() { int N; cin >> N; int M = (N-1)/3; // 整数除法，向下取整 int r = ( (N-1) % 4 * 3 ) % 4; // 计算余数r int count = 0; if (M < r) count = 0; else count = (M - r)/4 + 1; // 注意：这里除法是整数除法，向下取整 cout << count << endl; return 0; } 测试： N=1: M=0, r=0 -> count=(0-0)/4+1=0+1=1 N=2: M= (1)/3=0, r=(1%4*3)%4= (1*3)%4=3 -> 0<3 -> count=0 N=5: M=4/3=1, r=(4%4*3)%4=0 -> count=(1-0)/4+1=1/4+1=0+1=1 （注意：整数除法，1/4=0） N=100: M=99/3=33, r=(99%4*3)%4=(3*3)%4=9%4=1 -> count=(33-1)/4+1=32/4+1=8+1=9 所以两种方法都可以。 我们选择公式法（更高效，O(1)）。 但是，注意：整数除法在C++中对于非负数是向下取整。 所以，我们写公式法。 但是，注意：计算r的表达式：我们也可以写成 r = (3*(N-1)) % 4; 但是当N很大时，3*(N-1)可能溢出（但N最大10000，3*10000=30000，不会溢出int（int通常至少16位，一般32位））。所以没问题。 不过，我们可以用模运算性质：r = (3*(N-1)) % 4 = (3 * ( (N-1) % 4 )) % 4 （因为3*(a+4k) mod4 = (3a mod4)），所以两种写法都可以。 所以，我们写公式法。 最终代码： 注意：当N=0时，题目没有，所以不考虑。 代码：</think>### 解决方案 要解决这个问题，需要找出同时满足珂珂和乐乐喜欢的书籍数量。珂珂喜欢的书籍位置是1, 4, 7, ...（从前往后，间隔3），乐乐喜欢的书籍位置是N, N-4, N-8, ...（从后往前，间隔4）。共同喜欢的书籍位置需同时满足两个条件： - 位置 \( x = 1 + 3k \)（\( k \) 为非负整数，且 \( x \leq N \)） - 位置 \( x = N - 4j \)（\( j \) 为非负整数，且 \( x \geq 1 \)） 将两个等式结合： \[ 1 + 3k = N - 4j \] 整理得： \[ 3k + 4j = N - 1 \] 我们需要求解非负整数 \( (k, j) \) 的数量，其中 \( k \) 和 \( j \) 满足： - \( 3k \leq N-1 \)（即 \( k \leq \lfloor (N-1)/3 \rfloor \)） - \( 4j \leq N-1 \)（即 \( j \leq \lfloor (N-1)/4 \rfloor \)） #### 高效解法（数学公式） 通过数学推导，可以直接计算解的数量： 1. 计算 \( M = \lfloor (N-1)/3 \rfloor \)（\( k \) 的最大可能值）。 2. 计算余数 \( r = [3 \times (N-1)] \mod 4 \)（等价于 \( r = [(N-1) \mod 4 \times 3] \mod 4 \)）。 3. 如果 \( M < r \)，解的数量为 0。 4. 否则，解的数量为 \( \lfloor (M - r)/4 \rfloor + 1 \)。 #### C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int N; cin >> N; int M = (N - 1) / 3; // 整数除法向下取整 int r = ((N - 1) % 4 * 3) % 4; // 计算余数 r int count = 0; if (M < r) { count = 0; } else { count = (M - r) / 4 + 1; // 整数除法向下取整 } cout << count << endl; return 0; } ``` #### 代码解释 1. **输入处理**：读取书籍总数 \( N \)。 2. **计算 \( M \)**：\( M \) 是珂珂喜欢的书籍位置公式中 \( k \) 的最大可能值，即 \( M = \lfloor (N-1)/3 \rfloor \)。 3. **计算余数 \( r \)**： - 先计算 \( (N-1) \mod 4 \)，再乘以 3，最后对 4 取模，得到 \( r \)。 - 这等价于 \( r = [3 \times (N-1)] \mod 4 \)。 4. **判断解的数量**： - 如果 \( M < r \)，无解（`count = 0`）。 - 否则，解的数量为 \( (M - r)/4 + 1 \)（整数除法向下取整）。 5. **输出结果**：打印共同喜欢的书籍数量。 #### 示例验证 - **输入 \( N = 100 \)**： \( M = (100-1)/3 = 33 \)， \( r = ((99 \mod 4) \times 3) \mod 4 = (3 \times 3) \mod 4 = 1 \)， \( \text{count} = (33 - 1)/4 + 1 = 32/4 + 1 = 9 \)。 - **输入 \( N = 1 \)**： \( M = 0 \)， \( r = 0 \)， \( \text{count} = 1 \)。 - **输入 \( N = 2 \)**： \( M = 0 \)， \( r = 3 \)， \( \text{count} = 0 \)。 ### 相关问题