16 - 12 - 10 超时(Exceeding Time)问题优化

本文主要是介绍16 - 12 - 10 超时(Exceeding Time)问题优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、
Description
Kim刚刚学会C语言中的取模运算（mod）。他想要研究一下一个数字A模上一系列数后的结果是多少。帮他写个程序验证一下。
Input
第一行一个整数T代表数据组数。
接下来T组数据，第一行一个整数n，接下来n个数字ai
接下来一行一个整数m，接下来m个数字bi
Output
对于每个bi,输出bi%a1%a2%…%an
Sample
Input
1
4
10 9 5 7
5
14 8 27 11 25 4

Output
3
2
1
0

Hint
在C语言中，A mod B 是 a%b
样例解释：
14%10%9%5%7=4
8%10%9%5%7=3
数据范围：
1<=n<=100000
1<=m<=100000
1<=ai<=1000000000
0<=bi<=1000000000

↓ 普通方法不超时才怪。

<<<<<< 超时代码 >>>>>>

/*<<<<<< **超 时 代 码** >>>>>>*/#include<stdio.h>
#include<stdlib.h>
#include<cstring>
int main(){int T,i,n,m,j = 0;long a[100000],b[100000];scanf("%d",&T);while(T--){scanf("%d",&n);for(i = 0;i<n;i++){scanf("%d",&a[i]);}scanf("%d",&m);for(i = 0;i<m;i++){scanf("%d",&b[i]);}for(j = 0;j<m;j++){for(i = 0;i<n;i++){b[j] = b[j]%a[i];}printf("%d\n",b[j]);}memset(a,0,sizeof(a));memset(b,0,sizeof(b));n = 0;m = 0;}return 0;
}

<<<<<<正确代码>>>>>>

//<<<<<< **正 确 代 码** >>>>>>/*题解(来自哈理工官方网站)：中等题 。  注意到不断取模下去会越来越小，而且一个数模 a 之后再模b，如果 a 比 b 小那么模 b 就没有意义了。所以对输入的 a 数组剔除所有没用的数，剩下一个递减的数组。在这个数组上，每次二分找到距离当前x最接近且大于x的数，模上这个数重复这一过程即可。这个过程不会重复很多次。很快这个数就会小于所有的a，这时就获得了答案。*/#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#define left lll
#define right rrr#define FOR(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int a[200000+233];
int n,m;
long long  last,left,right,mid,q;
int main (int argc, char *argv[])
{int T;scanf("%d",&T);while (T--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);last=1;                            //？for(int i=2;i<=n;i++){if ( a[i] < a[last] ){last++;a[last]=a[i];}}n=last;scanf("%d",&m);for(i=1;i<=m;i++){   scanf("%lld",&q);while (1){        //是 1 不是 lleft=0;right=n+1;while ( right - left > 1 ){mid=(right+left)/2 ;if ( a[mid] <= q ){right = mid;}else left = mid;}if (right==n+1) break;q=q%a[right];}printf("%lld\n",q);}}return 0;
}