<?php

require( 'wp-load.php' );

set_time_limit( 0 ); // This is gonna take a while...

$posts = get_posts( array(
    'category_name' => 'm', // category slug
    'posts_per_page ' => -1, // all posts
) );

foreach ( $posts as $post ) {
    // Easier to get cat IDs using get_the_terms than get_the_category()
    $categories = array_keys( get_the_terms( $post->ID, 'category' ) );

    // Add the new category to the post's existing categories
    $categories[] = 123; // the ID of the category to add

    $updated_post = array();
    $updated_post['ID'] = $post->ID;
    $updated_post['post_category'] = $categories;

    wp_update_post( $categories );
}

echo 'Done!';

?>