結果
問題 | No.1201 お菓子配り-4 |
ユーザー |
![]() |
提出日時 | 2020-08-28 22:36:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,461 ms / 4,000 ms |
コード長 | 5,167 bytes |
コンパイル時間 | 1,332 ms |
コンパイル使用メモリ | 121,708 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 01:27:37 |
合計ジャッジ時間 | 28,931 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#line 2 "library/other/template.hpp"#define _CRT_SECURE_NO_WARNINGS#pragma target("avx2")#pragma optimize("O3")#pragma optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <ctime>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <list>#include <map>#include <memory>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <string.h>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define rep(i,n) for(int i=0;i<(n);i++)#define REP(i,n) for(int i=1;i<=(n);i++)#define all(V) V.begin(),V.end()typedef unsigned int uint;typedef long long lint;typedef unsigned long long ulint;typedef std::pair<int, int> P;typedef std::pair<lint, lint> LP;constexpr int INF = INT_MAX/2;constexpr lint LINF = LLONG_MAX/2;constexpr double eps = DBL_EPSILON;constexpr double PI=3.141592653589793238462643383279;template<class T>class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};template <class T, class U>inline bool chmax(T& lhs, const U& rhs) {if (lhs < rhs) {lhs = rhs;return 1;}return 0;}template <class T, class U>inline bool chmin(T& lhs, const U& rhs) {if (lhs > rhs) {lhs = rhs;return 1;}return 0;}inline lint gcd(lint a, lint b) {while (b) {lint c = a;a = b; b = c % b;}return a;}inline lint lcm(lint a, lint b) {return a / gcd(a, b) * b;}bool isprime(lint n) {if (n == 1)return false;for (int i = 2; i * i <= n; i++) {if (n % i == 0)return false;}return true;}template<typename T>T mypow(T a, lint b) {T res(1);while(b){if(b&1)res*=a;a*=a;b>>=1;}return res;}lint modpow(lint a, lint b, lint m) {lint res(1);while(b){if(b&1){res*=a;res%=m;}a*=a;a%=m;b>>=1;}return res;}template<typename T>void printArray(std::vector<T>& vec) {rep(i, vec.size()){std::cout << vec[i];std::cout<<(i==(int)vec.size()-1?"\n":" ");}}template<typename T>void printArray(T l, T r) {T rprev = std::prev(r);for (T i = l; i != rprev; i++) {std::cout << *i << " ";}std::cout << *rprev << std::endl;}LP extGcd(lint a,lint b) {if(b==0)return {1,0};LP s=extGcd(b,a%b);std::swap(s.first,s.second);s.second-=a/b*s.first;return s;}LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) {lint p=extGcd(m1,m2).first;lint tmp=(b2-b1)*p%m2;lint r=(b1+m1*tmp+m1*m2)%(m1*m2);return std::make_pair(r,m1*m2);}template<typename F>inline constexpr decltype(auto) lambda_fix(F&& f){return [f=std::forward<F>(f)](auto&&... args){return f(f,std::forward<decltype(args)>(args)...);};}#line 3 "library/algebraic/ModInt.hpp"class ModInt {lint value;public:constexpr static unsigned int modulo=1000000007;ModInt() : value(0) {}template<typename T>ModInt(T value = 0) : value(value) {if (value < 0)value = -(lint)(-value % modulo) + modulo;this->value = value % modulo;}//static inline void setMod(const unsigned int& mod){modulo=mod;}inline ModInt inv()const{return mypow(*this,modulo-2);}inline operator int()const { return value; }inline ModInt& operator+=(const ModInt& x) {value += x.value;if (value >= modulo)value -= modulo;return *this;}inline ModInt& operator++() {if (value == modulo - 1)value = 0;else value++;return *this;}inline ModInt operator-()const {return ModInt(0) -= *this;}inline ModInt& operator-=(const ModInt& x) {value -= x.value;if (value < 0)value += modulo;return *this;}inline ModInt& operator--() {if (value == 0)value = modulo - 1;else value--;return *this;}inline ModInt& operator*=(const ModInt& x) {value = value * x.value % modulo;return *this;}inline ModInt& operator/=(const ModInt& rhs) {return *this*=rhs.inv();}template<typename T> ModInt operator+(const T& rhs)const { return ModInt(*this) += rhs; }template<typename T> ModInt& operator+=(const T& rhs) { return operator+=(ModInt(rhs)); }template<typename T> ModInt operator-(const T& rhs)const { return ModInt(*this) -= rhs; }template<typename T> ModInt& operator-=(const T& rhs) { return operator-=(ModInt(rhs)); }template<typename T> ModInt operator*(const T& rhs)const { return ModInt(*this) *= rhs; }template<typename T> ModInt& operator*=(const T& rhs) { return operator*=(ModInt(rhs)); }template<typename T> ModInt operator/(const T& rhs)const { return ModInt(*this) /= rhs; }template<typename T> ModInt& operator/=(const T& rhs) { return operator/=(ModInt(rhs)); }};std::istream& operator>>(std::istream& ist, ModInt& x) {lint a;ist >> a;x = a;return ist;}#line 3 "main.cpp"int N,M;lint A[2010],B[2010];int main(){std::cin>>N>>M;rep(i,N)std::cin>>A[i];rep(i,M)std::cin>>B[i];ModInt ans=0;rep(i,N){rep(j,M){lint x=A[i]%B[j],g=gcd(x,B[j]),nmod=B[j]/g;ModInt rem=ModInt(g)*g*nmod*(nmod-1)/2;ans+=(ModInt(B[j]*(B[j]+1)/2)*A[i]-rem)/B[j]*2;}}std::cout<<ans<<std::endl;}