C++(g++ 7.5.0) 解法, 执行用时: 715ms, 内存消耗: 26448K, 提交时间: 2022-11-21 22:24:12

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 5e5 + 100;
const int mod = 20180718;
ll ans[N], s[N];

struct node {
	int l, r, id;
	bool operator<(const node &M) const {
		return r < M.r;
	}
} p[N];
ll a[N];

int main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		if (y >= 600) {
			ans[i] = 1;
			for (int j = x; j <= n; j += y)
				ans[i] = ans[i] * a[j] % mod;
		} else
			p[++cnt] = {x, y, i};
	}
	sort(p + 1, p + 1 + cnt);
	for (int i = 1; i <= cnt; i++) {
		if (p[i].r != p[i - 1].r) {
			int j;
			for (j = n; j >= n - p[i].r + 1; j--)
				s[j] = a[j];
			for (; j; j--)
				s[j] = s[j + p[i].r] * a[j] % mod;
		}
		ans[p[i].id] = s[p[i].l];
	}
	for (int i = 1; i <= m; i++)
		cout << ans[i] << '\n';
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 242ms, 内存消耗: 8196K, 提交时间: 2019-06-14 21:34:31

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rg register
inline int read(){
	rg char ch=getchar();
	rg int x=0,f=0;
	while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
int a[500050],n,m;
const int mod=20180718;
signed main(){
	n=read(),m=read();
	for(rg int i=1;i<=n;++i) a[i]=read();
	for(int x,y,k,i=1;i<=m;++i){
		x=read(),y=read();k=(n-x)/y;
		long long ans=1;
		for(int i=0;i<=k;++i) ans=(ans*a[x+i*y])%mod;
		printf("%lld\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 482ms, 内存消耗: 18128K, 提交时间: 2019-06-14 22:55:38

#include<cstdio>
#define ll long long 
#define mod 20180718
#define maxn 600005
ll a[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]=a[i]%mod;
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        ll ans=a[x]%mod;
        for(int j=1;x+j*y<=n;j++){
            ans=ans*a[x+j*y]%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}